Luogu2375 [NOI2014] 动物园

tony102

2021 年 08 月 02 日

1100 次浏览

暂无评论

798字数

题解

[Link](https://www.luogu.com.cn/problem/P2375)

## Description

子符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $num_i$，求出所有 $num_i$

## Sol

**重要性质：后缀同时又是它的前缀的数量 $f_i = f_{nxt_i - 1} + 1$**

实际上跟 [Luogu3435 [POI2006]OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435) 的性质很像，你可以知道，$nxt_i, nxt_{nxt_i},\dots$ 其实就是真前缀真后缀相等的长度，那每次递推往前求一下就得到了上面的式子。

注意判不相等，懒得讲了，这一部分我感觉网上的题解不是那么 naive

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 1e6 + 5;
const LL mod = 1e9 + 7;

int t, n;
int nxt[SIZE], f[SIZE];
char str[SIZE];

int main() {
	// freopen("code.in", "r", stdin);
	scanf("%d", &t);
	while (t --) {
		scanf("%s", str + 1);
		f[0] = 0, f[1] = 1, n = (int) strlen(str + 1);
		for (int i = 2, j = 0; i <= n; ++ i) {
			for ( ; j && str[i] != str[j + 1]; j = nxt[j]);
			if (str[i] == str[j + 1]) ++ j;
			nxt[i] = j, f[i] = f[j] + 1;
		}
		LL ans = 1ll;
		for (int i = 2, j = 0; i <= n; ++ i) {
			for ( ; j && str[i] != str[j + 1]; j = nxt[j]);
			if (str[i] == str[j + 1]) ++ j;
			for ( ; (j << 1) > i; j = nxt[j]);
			ans = (ans * (f[j] + 1ll) % mod) % mod;
		}
		printf("%lld\n", ans);
		for (int i = 0; i <= n; ++ i) f[i] = nxt[i] = 0;
	}
	return 0; 
}
```

最后修改：2021 年 09 月 07 日