HDU - 6153 A Secret 扩展kmp

题目链接：https://vjudge.net/problem/HDU-6153

题意：对于s2的每一个后缀，假设长度为l，在s1出现的次数为k，求l*k的和

题解：我们把两个串都倒过来，变为s1,s2，那么问题就变为，对于s2的前缀匹配s1的每个位置的后缀的总匹配长度和，举个栗子，s1: aaa s2: aa  那么在s1的位置1，能匹配的长度有1 2，因此我们扩展KMP求出最长长度l，把(1+l)*l/2累加起来即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000100;
const ll mod = 1e9 + 7;
int nex[N], ex[N];
void get_nex(char *s) {
int i = 0, j, pos, len = strlen(s);
nex[0] = len;
while(s[i] == s[i + 1] && i + 1 < len) i++;
nex[1] = i;
pos = 1;
for(i = 2; i < len; i++) {
if(nex[i - pos] + i < nex[pos] + pos)
nex[i] = nex[i - pos];
else {
j = nex[pos] + pos - i;
if(j < 0) j = 0;
while(i + j < len && s[j] == s[j + i]) j++;
nex[i] = j;
pos = i;
}
}
}
void ex_kmp(char *s, char *t) {
int i = 0, j, pos, l1 = strlen(s), l2 = strlen(t);
get_nex(s);
while(s[i] == t[i] && i < l1 && i < l2) i++;
ex[0] = i;
pos =
0;
for(int i = 1; i < l2; i++) {
if(nex[i - pos] + i < ex[pos] + pos)
ex[i] = nex[i - pos];
else {
j = ex[pos] + pos - i;
if(j < 0) j = 0;
while(i + j < l2 && j < l1 && s[j] == t[i + j]) j++;
ex[i] = j;
pos = i;
}
}
}
char cnt[N];
int main() {
char s[N], t[N];
int ls, lt;
int pos, len;
int T;
ll ans;
scanf("%d", &T);
while(T--) {
scanf("%s", cnt);
len = strlen(cnt);
lt = len;
for(int i = 0; i < len; i++)
t[len - i - 1] = cnt[i];
scanf("%s", cnt);
len = strlen(cnt);
for(int i = 0; i < len; i++)
s[len - i - 1] = cnt[i];
get_nex(s);
ex_kmp(s, t);
ans = 0;
for(int i = 0; i < lt; i++) {
//	cout << ex[i] << endl;
ans = (ans + 1LL*ex[i] * (ex[i] + 1) / 2) % mod;
}
printf("%lldn", ans);
}
return 0;
}

最后

以上就是纯真大碗为你收集整理的HDU - 6153 A Secret 扩展kmp的全部内容，希望文章能够帮你解决HDU - 6153 A Secret 扩展kmp所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。