BZOJ 3670 [Noi2014]动物园

Posted on | Edited on

题意

我现在希望求出一个更强大num数组一一对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。

然后输出$ _ {i = 1} ^ L (num[i] + 1) $

题解

这道题十分显然，求出nextx数组的同时求出自动机状态里的集合大小，然后枚举区间的右端点，满足题意不重叠的条件之后就可以算答案了。 ## 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <cstring>
#include <algorithm>

const int M = 1000000007;
int T;
int ans;
char s[2000000];
int n;
int nextx[2000000];
int k[2000000];

int main()
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%s", s + 1);
		n = strlen(s + 1);
		k[0] = 0;
		k[1] = 1;
		int j = 0;
		for (int i = 2; i <= n; i++)
		{
			while (j && s[j + 1] != s[i])
			{
				j = nextx[j];
			}
			if (s[j + 1] == s[i])
			{
				j++;
			}
			nextx[i] = j;
			k[i] = k[j] + 1;
		}
		j = 0;
		ans = 1;
		for (int i = 1; i <= n; i++)
		{
			while (j && s[j + 1] != s[i])
			{
				j = nextx[j];
			}
			if (s[j + 1] == s[i])
			{
				j++;
			}
			while (j > i / 2)
			{
				j = nextx[j];
			}
			ans = (long long)ans * (k[j] + 1) % M;
		}
		printf("%d\n", ans);
	}
	return 0;
}