扩展KMP

2020-03-07

字数统计: 566字 | 阅读时长≈ 3分钟

扩展KMP的总结

题目传送门：HDU-6153 A Secret

给定两个串，求其中一个串s的每个后缀在另一个串t中出现的次数乘以其长度之和。

1	#include <bits/stdc++.h>
2	using namespace std;
3	typedef long long ll;
4	const ll maxn = 1000005;
5	const ll mod = 1000000007;
6	ll nex[maxn], extend[maxn];
7	char a[maxn], b[maxn];
8	void pre_EKMP(char x[], ll m, ll nex[])
9	{
10	nex[0] = m;
11	ll j = 0;
12	while(j + 1 < m && x[j] == x[j + 1])j++;
13	nex[1] = j;
14	ll k = 1;
15	for(ll i = 2; i < m; i++){
16	ll p = nex[k] + k - 1;
17	ll L = nex[i - k];
18	if(i + L < p + 1)nex[i] = L;
19	else {
20	j = max((ll)0, p - i + 1);
21	while(i + j < m && x[i + j] == x[j])j++;
22	nex[i] = j;
23	k = i;
24	}
25	}
26	}
27	void EKMP(char x[], ll m, char y[], ll n, ll nex[], ll extend[]){
28	pre_EKMP(x, m, nex);
29	ll j = 0;
30	while(j < n && j < m && x[j] == y[j])j++;
31	extend[0] = j;
32	ll k = 0;
33	for(ll i = 1; i < n; i++)
34	{
35	ll p = extend[k] + k - 1;
36	ll L = nex[i - k];
37	if(i + L < p + 1)extend[i] = L;
38	else
39	{
40	j = max((ll)0, p - i + 1);
41	while(i + j < n && j < m && y[i + j] == x[j])j++;
42	extend[i] = j;
43	k = i;
44	}
45	}
46	}
47	int main()
48	{
49	ll t, n, m, i;
50	scanf("%lld", &t);
51	while(t--)
52	{
53	scanf("%s %s", a, b);
54	n = strlen(a), m = strlen(b);
55	for(i = 0; i < n / 2; i++)swap(a[i],a[n - 1 - i]);
56	for(i = 0; i < m / 2; i++)swap(b[i],b[m - 1 - i]);
57	EKMP(b, strlen(b), a, strlen(a), nex, extend);
58	ll ans = 0;
59	for(i = 0; i < n; i++)
60	{
61	ans += (1 + extend[i]) * extend[i] / 2;
62	ans %= mod;
63	}
64	printf("%lld\n", ans);
65	}
66	}