链接:
https://vjudge.net/problem/HDU-2594#author=0
题意:
求S1的前缀和S2的后缀的《最大》匹配
思路:
kmp方法:
将s1, s2首尾连接, 根据Next数组求, 注意长度要比s1, 和s2的长度小.
ExtenKmp:
考虑以s1为模板串, 匹配s2, 对于第一个满足exten[i]+i == len的点, 就为最长的长度.
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
//#include <memory.h>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <stack>
#include <string>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <sstream>
#define MINF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;char s1[MAXN], s2[MAXN];
int Next[MAXN];void GetNext(char *s)
{int j = 0;int k = -1;int len = strlen(s);Next[0] = -1;while (j < len){if (k == -1 || s[j] == s[k]){++j;++k;Next[j] = k;}elsek = Next[k];}
}int main()
{while (~scanf("%s%s", s1, s2)){int lens1 = strlen(s1);int lens2 = strlen(s2);strcat(s1, s2);GetNext(s1);int ans = Next[strlen(s1)];while (ans > lens1 || ans > lens2)ans = Next[ans];if (ans == 0 || ans == -1)puts("0");else{s1[ans] = 0;printf("%s %d\n", s1, ans);}}return 0;
}ExtenKmp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
//#include <memory.h>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <stack>
#include <string>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <sstream>
#define MINF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;char s1[MAXN], s2[MAXN];
int Next[MAXN], Exten[MAXN];void GetNext(char *s)
{int len = strlen(s);int a = 0, p = 0;Next[0] = len;for (int i = 1;i < len;i++){if (i >= p || i+Next[i-a] >= p){if (i >= p)p = i;while (p < len && s[p] == s[p-i])p++;Next[i] = p-i;a = i;}elseNext[i] = Next[i-a];}
}void ExKmp(char *s, char *t)
{int len = strlen(s);int a = 0, p = 0;GetNext(t);for (int i = 0;i < len;i++){if (i >= p || i + Next[i-a] >= p){if (i >= p)p = i;while (p < len && s[p] == t[p-i])p++;Exten[i] = p-i;a = i;}elseExten[i] = Next[i-a];}}int main()
{while (~scanf("%s%s", s1, s2)){ExKmp(s2, s1);int len = 0, p = 0;int lens = strlen(s2);for (int i = 0;i < lens;i++){if (Exten[i]+i == lens){len = Exten[i];p = i;break;}}if (len == 0)puts("0");elseprintf("%s %d\n", s2+p, len);}return 0;
}
