题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2594
题目大意:给定两个字符串s1,s2,求最长的s1前缀ss使得ss为s2的后缀,比如s1 = "youloveme",s2 = "fuckyou",所求ss即为“you"
题目思路:将s1和s2拼为s3,在s3中求next数组,最终判断最后一个字母的next值,我的代码中next+1才代表自身匹配数
测试数据::
abc abcd
hellolleh hello
hello ello
ello hello
hellolleh olleh
clinton homer
aaaaa aaaaaa
clinton homer
riemann marjorie
abcba bcba
代码:
#include <stdio.h> #include <string.h> #define MAX 50010 int next[MAX*2],maxx,l1,l2; char s1[MAX],s2[MAX],s3[MAX*2],ans[MAX]; void getnext(char *s) { int i,j,k; i = 0,j = -1; next[0] = -1; while (s[i]) { if (j == -1 || s[i] == s[j]) i++,j++,next[i] = j; else j = next[j]; } if (next[i] > -1) { maxx = next[i]; for (j = 0; j < maxx; ++j) ans[j] = s[j]; ans[j] = '\0'; } } void Solve() { strcpy(s3,s1); strcat(s3,"*"); strcat(s3,s2); getnext(s3); } int main() { int i,j,k; while (scanf("%s%s",s1,s2) != EOF) { memset(next,-1,sizeof(next)); maxx = -2; l1 = strlen(s1); l2 = strlen(s2); Solve(); if (maxx <= 0) printf("0\n"); else printf("%s %d\n",ans,maxx); } }