Chapter 7. 字符串  KMP

Sylvia's  I.

  我们储存的字符串从标号1开始

  关于Next数组的作用，贴一个博客：http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html 

 

  那么该如何计算Next

 代码是最好的语言.

void GetNext(char p[],int lenp){//p[]是模式串，lenp是p[]的长度    int j=0;//j记录的是已经匹配的字符数，初始并没有匹配    Next[1]=0;//对于任意单独的一个字符，它前缀和后缀都为空集，共有元素的长度为0    for (int i=2;i<=lenp;i++){        while (j&&p[i]!=p[j+1]) j=Next[j];//注释①        if (p[j+1]==p[i]) j++;//如果下一位匹配成功，那么j（已经匹配的字符数加一）        Next[i]=j;//注释②    }}

注释①：计算Next数组实质上是p的自我匹配，但是模式串是不断变化的，为什么这么说呢，比如p=‘ABABABCA’

       “主串”              “模式串”（ i 指向的是这里的”模式串“）

i=2 ABABABCA  BABABCA  Next[2]=0 失配

i=3 ABABABCA  ABABCA    Next[3]=1 ，然后会匹配“模式串”中第二位和”主串“中的第二位，i=4 Next[4]=2，然后匹配第三位i=5 Next[5]=3,匹配第四位，i=6，Next[6]=4,匹配第五位，失配

i=7 ABABABCA  CA            Next[6]=0. 失配

i=8 ABABABCA  A              Next[7]=1. 

最终Next={0,0,1,2,3,4,0,1}

在匹配的过程中，一旦失配，模式串就会变化，当然这只是我们将过程形象化而已，程序中的实现中是一旦失配，是将j变化从而实现”模式串“的变化，j跳转至当前字符之前字符串的最长公共前缀后缀最后一个字符，直至j=0或者下一位匹配成功，有点绕……

比如，ABDABCD Next={0,0,0,1,2,0,0} 假如此时j=5，指向B,此时下一位C失配了，我们就将j就跳转至此字符（B）之前字符串（ABDAB）的最长公共前缀后缀（AB）最后一个字符（B），那么j就指向了第一个B,对于这句话的赋值就是j=Next[j]，那么赋值后也就是j=2了，如果下一位继续失配，那么继续跳转。

 

注释②：当前Next就是已经匹配的位数，就是j

Sylvia's II.

   关于KMP

void KMP(char t[],int lent,char p[],int lenp){//t主串，p模式串    int j=0;//j指向p，表示已经匹配的位数    for (int i=1;i<=lent;i++){//i指向t        while (j&&p[j+1]!=t[i]) j=Next[j];//如果失配，跳转        if (p[j+1]==t[i]) j++;//匹配成功一位，j+1        if(j==lenp) {//如果匹配完成            printf("%d\n",i-lenp+1);//输出位置            j=Next[j];//跳转，继续匹配        }    }}

 

Sylvia’s III.

完整代码： 

//洛谷p3375//给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。//并输出前缀数组Next //标号1开始#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define debug(x) cerr<<#x<<'='<
          
           <
          
         
        
       
      
     

 

 再贴一个从标号0开始的

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define debug(x) cerr<<#x<<'='<
          
           <
           
            0&&p[j]!=p[i]) j=Next[j]; if (p[i]==p[j]) j++; Next[i+1]=j; //这里的不同，但是Next数组都是从1开始存储的 }}void KMP(char t[],int lent,char p[],int lenp){ int j=0; for (int i=0;i
            
             0&&p[j]!=t[i]) j=Next[j]; if (t[i]==p[j]) j++; if (j==lenp){ printf("%d\n",i-lenp+2);//输出也不同 j=Next[j]; } }}int main (){ scanf("%s",target); scanf("%s",pattern); lenp=strlen(pattern); lent=strlen(target); GetNext(pattern,lenp); KMP(target,lent,pattern,lenp); for (int i=1;i<=lenp;i++){ printf("%d ",Next[i]); } return 0;}
            
           
          
         
        
       
      
     

 

 

---

 

 

不负我心

三毛

心之如何

有似万丈迷津

遥亘千里

其中并无舟子可以渡人

除了自渡

他人爱莫能助

 

---

 

Sylvia

二零一七年六月一日