题意:
求一个长串最多可以被分成几个子串.
思路:
kmp, 只是不能重叠. 匹配成功后 j 回溯到 -1 而不是到 next [ j ]
#include <cstring> #include <cstdio> const int MAXN = 1005; int next[MAXN],ans; char s[MAXN]; char a[MAXN]; //0MS 204K void prekmp() { next[0] = -1; int j = -1; for(int i=1;s[i];i++) { while(j!=-1 && s[j+1]!=s[i]) j = next[j]; if(s[j+1]==s[i]) j++; next[i] = j; } } void kmp() { int j=-1; ans = 0; for(int i=0;a[i];i++) { while(j!=-1 && s[j+1]!=a[i]) j = next[j]; if(s[j+1]==a[i]) j++; if(!s[j+1]) { ans++; j = -1; } } } int main() { while(scanf("%s",a) && a[0]!='#') { scanf("%s",s); prekmp(); kmp(); printf("%d\n",ans); } }