KMP字符串匹配算法及Java实现

KMP算法的Java实现：

1. KMP算法的思路：
1) 首先对模式串构建next数组，表示当某一位不匹配的时候需要回溯的下一个位置；
2) 然后在对主串使用该模式串进行匹配，当遇到不相等的地方，查询next数组，选择模式串中下一个要匹配的位置的字符；
如果该字符和当前不匹配的字符一样的话，则进一步获取新位置在next数组的值，直到要匹配位置的字符是新的字符；
(不要此步骤也可以，此步骤更加优化)
3) 直到到达模式串结尾。

KMP算法的复杂度：

首先生成匹配字符串的next数组的时间复杂度为，每个元素的前面部分元素都需要检查前后是否相等，因此为
1/2*(1+m)*m/2=m(1+m)/4，因此为o(m2);
匹配阶段，每个主字符串位置移动，因此为o(n);
整个为o(m2+n);


KMP算法的Java实现：

class KMP
{
    String s; //主字符串
    String p; //匹配字符串
    int[] next; //匹配字符串的next数组
   
    int times; //记录匹配的次数
    int index; //记录查找到的位置
   
    KMP(String s,String p) //构造函数，初始化各个成员变量
    {
        this.s=s;
        this.p=p;
        this.next=new int[p.length()];
        for(int i=0;i<p.length();i++)
        {
            if(i==0)
            {
                this.next[i]=-1;
            }else if(i==1)
            {
                this.next[i]=0;
            }
            else
            {
                this.next[i]=next(p.substring(0,i)); //对某个位置之前的字符串考察其开始部分和结尾部分是否相同
            }
        }
       
        this.times=0;
        this.index=-1;
    }
   
    private int next(String p)  //返回子字符串，开始部分和结尾部分相同的情况下的开始部分的下一个位置，即next值
    {
        int length=p.length()/2;
       
        while(length>0)
        {
            if(p.substring(0,length).compareTo(p.substring((p.length()-length),p.length()))==0)
            {
                return length;
            }
            length--;
        }
        return length;
    }
   
//对主字符串进行比较，碰到不匹配，查询next数组；如果新元素和当前不匹配元素相同，则继续next
    boolean match()
    {
        int i=0;
        int j=0;
        int index=-1; //index记录匹配的位置
       
        while(i<this.s.length()&&j<this.p.length())
        {
            if(this.s.charAt(i)==this.p.charAt(j))
            {
                if(j==0){
                    index=i;
                }
               
                i++;
                j++;
            }
            else
            {
                //一直寻找next，知道和当前元素不相等的元素，将其下标赋值给j
                int newj=this.next[j];
                while((newj!=-1)&&(this.p.charAt(newj)==this.p.charAt(j)))
                {
                    newj=this.next[newj];
                }
                j=newj;
               
                if(j==-1)
                {
                    i++;
                    j=0;
                }
                else
                {
                    index=i-j;
                }
            }
            this.times++;
        }
       
        if(j==this.p.length())
        {
            this.index=index;
            return true;
        }
        else
        {
            return false;
        }
    }
}

//应用实例
class Test
{
    public static void main(String[] args)
    {
        String s="abacsbababbcacs";
        String p="ababbcac";
        KMP m=new KMP(s, p);
       
        //顺便打印next数组；
        for(int i=0;i<m.next.length;i++)
        {
            System.out.println(m.next[i]+" ");
        }
       
        if(m.match())
        {
            System.out.println("match");
            System.out.println("match times: "+m.times);
            int index=m.index;
            System.out.println(index);
        }
        else
        {
            System.out.println("not match");
        }
       
    }
}