http://acm.pku.edu.cn/JudgeOnline/problem?id=2752
昨天写完以后WA了好几次，今天发现边界条件的判断有问题，就修改了一下，结果又RE了几次。然后把数组改大了一些就ac了。看来开数组真不能小气呀！要把数组开的尽量大一些。
kmp最关键的地方就是理解目标字符串匹配的过程。假设目标字符串是ababde，dist[i]表示当匹配到第i个字符后匹配失败应用第几个字符与下一个字符匹配。那么dist[1] = 1(只匹配成功了第一个字符，那就拿第一个字符跟下一个字符比较)，dist[2] = 1,dist[3] = 2(由于aba匹配成功，那么下次匹配时可以直接拿b，也就是第二个字符跟下一个字符比较),dist[4]=3,dist[5]呢？我们发现当ababd匹配成功时，第三个字符a和d不相等，怎么办？我们现在相当于进入了另外一个匹配过程：我们的目标字符串匹配到ab后失败了，那么就取dist[2] = 1，拿a跟d比，发现仍然不相同，那就只好取dist[5]=1了，也就是下次匹配拿第一个字符跟下一个字符比。
不过这个题之需要把dist[]数组求出来即可，我的dist[]数组有点儿问题，边界设置的不太好，dist[0] = -1，对这个题来说无所谓，不过真的要匹配的话就得将数组值加1来计算。
#include<stdio.h> #include<string.h> char s[500000]; int result[400000],dist[500000]; int main() { int i,j,k,str_length; char *p = s; while(scanf("%s",p) != EOF) { result[0] = 0; k = -1; dist[0] = -1; str_length = strlen(p); for (i = 1;i < str_length;i++) { while(k >= 0 && s[k+1] != s[i]) k = dist[k]; if (s[k+1] == s[i]) k++; dist[i] = k; } j = dist[str_length-1]; while(j >= 0) { result[0]++; result[result[0]] = j+1; j = dist[j]; } for (i = 0;i < result[0];i++) { printf("%d ",result[result[0] - i]); } printf("%d\n",str_length); } return 0; }
转载于:https://www.cnblogs.com/xinguohenan/archive/2009/05/15/1457959.html
