HDU2594 KMP next数组的应用

这道题就是给你两个串s1, s2让你求出s1 s2的最长相同前缀和后缀， 我们直接将s1 s2连接到一起然后处理一下next数组即可， 注意答案应该是min(len(s1), len(s2) , next[len]), 代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
char str[100000 + 100];
int len;
int nxt[100000 + 100];
void getnext(){int i=0, j=-1;nxt[0] = -1;while(i<len){if(j==-1 || str[i]==str[j])nxt[++i] = ++j;else j = nxt[j];}
}
int main() {while(scanf("%s", str) != EOF){len = strlen(str);int len1 = len;scanf("%s", str+len);len = strlen(str);int len2 = len-len1;//        printf("%s\n", str);
        getnext();
//        for(int i=0; i<=len; i++) printf("%d ", next[i]);
//        printf("\n");if(nxt[len] == 0) printf("0\n");else {int tp1 = min(len1, len2);int tp2 = min(tp1, nxt[len]);for(int i=0; i<tp2; i++) printf("%c", str[i]);printf(" %d\n", tp2);}}return 0;
}