HDU 2594 Simpsons’ Hidden Talents kmp || extkmp

题目：

http://acm.hdu.edu.cn/showproblem.php?pid=2594

题意：

给定两个字符串 s1,s2 ，求 s1 的前缀和 s2 的后缀相等的最大长度

思路：

kmp 的话，直接用 s1 去匹配 s2 即可。 extkmp 的话，也是用 s1 去匹配 s2 ，从前往后，找到一个 i+extend[i]=len 的第一个位置即可 kmp：

#include <bits/stdc++.h> using namespace std; const int N = 50010; char pat[N], ori[N]; int Next[N]; void get_next(char *pat) { int i = 0, j = -1; Next[0] = -1; while(pat[i]) { if(j == -1 || pat[i] == pat[j]) Next[++i] = ++j; else j = Next[j]; } } int kmp(char *ori, char *pat) { get_next(pat); int i = 0, j = 0; while(ori[i]) { if(j == -1 || ori[i] == pat[j]) ++i, ++j; else j = Next[j]; } return j; } int main() { while(~ scanf("%s%s", pat, ori)) { int ans = kmp(ori, pat); if(ans == 0) printf("0\n"); else { for(int i = 0; i < ans; i++) printf("%c", pat[i]); printf(" %d\n", ans); } } return 0; }

extkmp：

#include <bits/stdc++.h> using namespace std; const int N = 50000 + 10, INF = 0x3f3f3f3f; char ori[N], pat[N]; int Next[N], extend[N]; void get_next(char *pat) { int len = strlen(pat); Next[0] = len; int k = 0; while(k + 1 < len && pat[k] == pat[k+1]) ++k; Next[1] = k; k = 1; for(int i = 2; pat[i]; i++) { if(i + Next[i-k] < k + Next[k]) Next[i] = Next[i-k]; else { int j = max(k + Next[k] - i, 0); while(i + j < len && pat[j] == pat[i+j]) ++j; Next[i] = j; k = i; } } } void extkmp(char *ori, char *pat) { get_next(pat); int leno = strlen(ori), lenp = strlen(pat); int k = 0; while(k < leno && k < lenp && ori[k] == pat[k]) ++k; extend[0] = k; k = 0; for(int i = 1; ori[i]; i++) { if(i + Next[i-k] < k + extend[k]) extend[i] = Next[i-k]; else { int j = max(k + extend[k] - i, 0); while(i + j < leno && j < lenp && ori[i+j] == pat[j]) ++j; extend[i] = j; k = i; } } } int main() { while(~ scanf("%s%s", pat, ori)) { extkmp(ori, pat); int leno = strlen(ori); int ans = 0; for(int i = 0; ori[i]; i++) if(i + extend[i] == leno && extend[i] > ans) { ans = extend[i]; break; } pat[ans] = '\0'; if(ans == 0) printf("%d\n", ans); else printf("%s %d\n", pat, ans); } return 0; }