Leetcode KMP算法中next数组的求解

KMP算法可以在O(m+n)的时间复杂度内，求解模式串在匹配串中的位置，其关键是模式串next数组的求解。

对于一个模式串P.  满足

• P的前缀k部分子串(p[0].....p[k-1]) 
• P的后缀k部分子串(p[last-k+1].....p[last])

两部分子串相等的最大K 称为模式串P的最大前缀后缀匹配长度

 

next数组：

表示模式串的各部分子串的最大前缀后缀长度的数组

即：next[i]表示p[0]....p[i]子串的最大前缀后缀长度

 

kmp算法求解next思路：采取动态规划的思路

当前求解位置： next[i]   那么之前的next[0].....next[i-1]已知：

容易直到 p[0]到p[i-1]部分的子串 的最大前缀后缀长度为 next[i-1] 设为pre

即 

• ①p[0]到p[pre-1]   
• ②p[i-pre+1]到p[i]   

相等

那么下一步需要研究 p[pre]与p[i]()当前字符的关系

若p[pre]==p[i]  那么可以在next[i-1]基础上+1  即 next[i]=next[i-1]+1

 

 

若p[pre]!=p[i]   那么pre=next[pre-1]  ，直到p[pre]=p[i]  

其含义为：由于①与②两部分相等，那么回退寻找匹配的过程等价于①部分的最大前缀后缀长度（子问题）

 

生成next数组代码：

    int next[1000];//next数组 
    void make_next(string p)
    {
        next[0]=0;//即p[0]单独一个字符 没有前缀后缀概念
        
        int k=0;
        for(int i=1;i<p.size();i++)
        {
            while(k>0 && p[k]!=p[i])  //从最长的可能前缀后缀匹配开始  如果失败  回退部分
                k=next[k-1];
            
            if(p[k]==p[i])
                k++;  //匹配增加一个
            next[i]=k;     
        }
    }

 

由next数组求解字符串匹配代码：

 

 

 

  int kmp(string s,string p)  //kmp算法 ：返回s串中p第一次出现的位置  没有返回-1
    {
        int size1=s.size();
        int size2=p.size();
        if(size1==0 || size2==0)
            return -1;
        make_next(p);

        int i=0;
        int j=0;
        while(i<size1 && j<size2)
        {
           
            if(s[i]==s[j])
            {
                i++;
                j++;
                	
            }
            else  //匹配失败
            {
                if(j==0)  //第一个就不等
                {
                      i++;
		}
                else
                {
                	
                	  j=next[j-1]; 
                 //模式串定位到j位置(已匹配部分的next大小)与字符串当前i位置比较  
                         
                 //因为模式串j位置之前一定可以匹配
		}
                 
                
            }
            
            
            
        }
        if(j==size2)
            return i-j; 
        else
            return -1;

        
    }