C++之路进阶——kmp（寻找子串位置）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<string>
 4 #define maxn 10000
 5 
 6 using namespace std;
 7 
 8 int p[maxn];
 9 
10 int main()
11   {
12       string a,b;
13       cin>>a>>b;
14       int n=a.length();
15       int m=b.length();
16       a=" "+a;
17       b=" "+b;
18       int j=0;
19       for (int i=2;i<=m;i++)
20          {
21                 while (j>0&&b[j+1]!=b[i]) j=p[j];
22                 if (b[j+1]==b[i])j++; 
23                 p[i]=j;
24           } 
25     j=0;
26     for (int i=1;i<=n;i++)
27        {
28               while (j>0&&b[j+1]!=a[i]) j=p[j];
29               if (b[j+1]==a[i]) j++;
30            if (j==m) {printf("%d",i-m+1);return 0;}       
31              }      
32   }