A[1~N] 是否为 B[1~M] 的子串
- next[1]=0;
- for(int i=2,j=0;i<=n;i++)
- {
- while(j>0&&a[i]!=a[j+1]) j=next[j];
- if(a[i]==a[j+1]) j++;
- next[i]=j;
- }
- for(int i=1,j=0;i<=m;i++)
- {
- while(j>0&&(j==n||b[i]!=a[j+1])) j=next[j];
- if(b[i]==a[j+1]) j++;
- f[i]=j;
- //if(f[i]==n) A 在 B 中出现一次
- }
来源: http://www.bubuko.com/infodetail-3386902.html