经典的KMP算法

「爱情、让人受尽委屈。」 2022-05-28 00:21 146阅读 0赞

![20180326193937367][]

![20180326152615893][]

//KMP算法(手写大名鼎鼎的kmp)经典的KMP算法时间复杂度为O(m+n)
    public class kmp{
    	
        //kmp算法查找是否匹配
        public static int getIndexOf(String s,String m)
        {
        	 if(s==null||m==null||m.length()<1||s.length()<m.length())
        	 {
        	 	 return -1;
        	 }
        	 char[]ss=s.toCharArray();  //字符串转换为数组
        	 char[]ms=m.toCharArray();
        	 int si=0;
        	 int mi=0;
        	 int[]next=getNextArray(ms); //获得next数组
        	 while(si<ss.length&&mi<ms.length)
        	 {
        	 	 if(ss[si]==ms[mi])
        	 	 {
        	 	 	si++;
        	 	 	mi++;
        	 	 }else if(next[mi]==-1)
        	 	 {
        	 	 	si++;
        	 	 }else{
        	 	 	mi=next[mi];
        	 	 }
        	 }
        	 return mi==ms.length?si-mi:-1;
    
        }
    
        public static int[]getNextArray(char[]ms)
        {
         	if(ms.length==1)
         	{
         		 return new int[]{-1};
         	}
         	int []next=new int[ms.length];
         	next[0]=-1;
         	next[1]=0;
         	int pos=2; //当前所指位置
         	int cn=0;
         	while(pos<next.length)
         	{
                 if(ms[pos-1]==ms[cn])
                 {
                 	next[pos++]=++cn;
                 }else if(cn>0)
                 {
                 	cn=next[cn];
                 }else
                 {
                 	  next[pos++]=0;
                 }
         	}
    
            return next;
        } 
    	 public static void main(String[]args)
    	 { 
    	 	String s="abcdef"; //主串
    	 	String t="cde";    //模式串
    	 	System.out.println(getIndexOf(s,t));
              
    	 }
    }

![20180326152704769][]

next\[cn\]表示它之前字符串(cn-1个字符)的最大匹配长度

[20180326193937367]: /images/20220528/3b2cd6bdaf414116848ff0c930277d94.png
[20180326152615893]: /images/20220528/c40f577643e643c68d260a6897b99eca.png
[20180326152704769]: /images/20220528/fa02e1a348cf42479f25eb72a729daff.png