KMP算法 KMP模式匹配 二（串）

Description

输入一个主串和一个子串，用KMP进行匹配，问进行几趟匹配才成功，若没成功，则输出0

Input

输入一个主串和一个子串

Output

匹配的趟数

Sample Input

ababcabcacbab
abcac

Sample Output

3

今早晨看了一遍才算真正看懂了代码。next数组的求值。。

#include
  
   
#include
   
     #include
    
      using namespace std; int next[10005]; char str[10005]; int len; void getnext(char *str,int next[]) { int j,k; next[1]=0; j=1; k=0; while(j<=len) if((k==0)||(str[j]==str[k])) { ++j; ++k; next[j]=k; } else k=next[k]; } int main() { char s[1005]; cin>>s; len =strlen(s); int j,k; for(j=1,k=0;k