題目鏈接:hdu 2954 Simpsons’ Hidden Talents
題目大意:給出兩個字符串,找出一個子串,為s1的前綴,s2的後綴, 要求子串最長,並且輸出該子串。
解題思路:將s1和s2首尾相連,然後求出next數組的next[n+m]的位置,然後和n、m取最小值即為答案。
#include#include #define min(a,b) (a)<(b)?(a):(b) const int N = 1e5+5; int n, m, next[N]; char s1[N], s2[N]; void getNext () { int p = 0; m = strlen(s1+1); for (int i = 2; i <= m; i++) { while (p > 0 && s1[p+1] != s1[i]) p = next[p]; if (s1[p+1] == s1[i]) p++; next[i] = p; } } int main () { while (scanf("%s%s", s1+1, s2+1) == 2) { n = min (strlen(s1+1), strlen(s2+1)); strcat (s1+1, s2+1); getNext (); int ans = min (next[m], n); for (int i = 1; i <= ans; i++) printf("%c", s1[i]); if (ans) printf(" "); printf("%d\n", ans); } return 0; }