[NOI2014]动物园 题解（预览）

一开始读错题了淦。

---

对于一个位置 (i)， (num[i]) 显然是满足条件的最大前缀长 (k) 用 (next[k]) 跳到 (0) 需要的次数。

对每个 (i) 如何求 (k)？ 类比 (next) 的递推方式， 只需要加个限制长度的 (while) 语句就可以求出 (k) 了。（(i) 的 (k) 用 (i-1) 的 (k) 推出即可，至于为什么，画一画qwq）

如何计数一个位置 (s) 用 (nxt) 跳到 (0) 的次数？可以发现若对于每个 (s)，将 (nxt[s]) 到 (s) 连一条有向边， 所形成的结构就是一棵树， 其中， 入度为 (0) 的节点为 (0)， 且 (s) 用 (nxt) 跳到 (0) 需要跳的次数就是以 (0) 为根时 (s) 的深度。

---

luogu数据AC代码

#include<bits/stdc++.h>
using namespace std;
#define li long long
const int maxn = 1e6+5;
const int mod = 1000000007;

int len, nxx[maxn], nxt[maxn];
char s[maxn];

int ct, hed[maxn], nx[maxn<<1], ver[maxn<<1];
void ad(int a,int b) {
	ver[++ct] = b;
	nx[ct] = hed[a];
	hed[a] = ct;
}
int dep[maxn];
void dfs(int x,int Dep) {
	dep[x]=Dep;
	for(int i=hed[x];i;i=nx[i]) {
		int y=ver[i];
		dfs(y,Dep+1);
	}
}

int main()
{
	int n; cin>>n; while(n--) {
		ct = 0;
		memset(hed,0,sizeof hed);
		scanf("%s", s+1); len=strlen(s+1);
		nxt[1]=0;
		for(int i=2,j=0;i<=len;++i) {
			while(j&&s[j+1]!=s[i]) j=nxt[j];
			if(s[j+1]==s[i]) ++j;
			nxt[i]=j;
		}
		nxx[1]=0;
		for(int i=2,j=0;i<=len;++i) {
			while(j+1>i/2) j=nxt[j];
			while(j&&s[j+1]!=s[i]) j=nxt[j];
			if(s[j+1]==s[i]) ++j;
			nxx[i]=j;
		}
		//
		for(int i=1;i<=len;++i) ad(nxt[i],i);
		dfs(0,1);
		li ans = 1ll;
		for(int i=1;i<=len;++i) ans = ans*1ll*dep[nxx[i]]%mod;
		cout<<ans<<'
';
	}
	return 0;
}