Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1502
一道KMP算法题，第一次写，照葫芦画瓢地完成了。
贴代码：
[已更新]
#include <iostream> #include <cstring> using namespace std; char sa[100005],sb[100005]; int next[100005]; void getnext(int lb) { int i=0,j=-1; next[0] = -1; while (i<lb) { if (j==-1 || sb[i]==sb[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } } int kmp(int pos, int la, int lb) { int i=pos,j=0; getnext(lb); while (i<la && j<lb) { if (j==-1 || sa[i]==sb[j]) { i++; j++; } else { j = next[j]; } } if (j>=lb) return lb; else return j; return 0; } int main() { int len,la,lb; while(scanf("%s", sa)!=EOF) { scanf("%s", sb); la = strlen(sa); lb = strlen(sb); len = la>lb?kmp(la-lb,la,lb):kmp(0,la,lb); printf("%d/n", len); } return 0; }
