【BZOJ3670】【UOJ5】【NOI2014】动物园

【题目链接】

• BZOJ
• UOJ

【思路要点】

• 做两次KMP，第一次求出Next数组，第二次保证匹配位数不超过当前串的一半（否则视为失配），求出Num数组。
• 时间复杂度\(O(NL)\)。

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN	1000005
#define P   1000000007
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
char s[MAXN];
int len[MAXN], num[MAXN], nxt[MAXN];
int main() {
	int T; read(T);
	while (T--) {
		scanf("\n%s", s + 1);
		int n = strlen(s + 1);
		nxt[1] = 0; num[1] = 1;
		for (int i = 2; i <= n; i++) {
			int j = nxt[i - 1];
			while (j && s[i] != s[j + 1]) j = nxt[j];
			if (s[i] == s[j + 1]) j++;
			nxt[i] = j; num[i] = num[j] + 1;
		}
		long long ans = 1;
		int pos = 0;
		for (int i = 2; i <= n; i++) {
			while (pos && s[i] != s[pos + 1]) pos = nxt[pos];
			if (s[i] == s[pos + 1]) pos++;
			if (pos > i / 2) pos = nxt[pos];
			ans = ans * (num[pos] + 1) % P;
		}
		printf("%lld\n", ans);
	}
	return 0;
}