[NOI2014] 动物园

青烟绕指柔!

于 2021-06-22 13:28:28 发布

阅读量272

点赞数

分类专栏：字符串思维题

本文链接：https://blog.csdn.net/weixin_43826249/article/details/118105096

版权

思维题同时被 2 个专栏收录

136 篇文章

订阅专栏

字符串

19 篇文章

订阅专栏

这篇博客介绍了一种利用Border树解决字符串子串计数的方法。代码中展示了如何构建和遍历Border树，通过维护从根节点到当前节点的节点栈，有效地向下传递信息。AC代码实现了字符串模式匹配，并在O(n)的时间复杂度内计算了所有子串出现的次数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接：[NOI2014] 动物园

维护一个border 树，然后对于每个点，继承父亲的答案，暴力向下跳即可。
因为由于border树的性质，跳到的全是当前点的border
为了方便向下跳，我们维护一个根节点到当前节点的节点栈

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int n,q,fail[N],res[N],ans; char str[N];
vector<int> g[N],v;
void dfs(int x,int fa){
	res[x]=res[fa];
	while(res[x]<v.size()-1&&v[res[x]+1]*2<=x) res[x]++;
	for(int to:g[x]){
		v.push_back(to);
		dfs(to,x);
		v.pop_back();
	}
}
void solve(){
	scanf("%s",str+1); n=strlen(str+1); ans=1;
	for(int i=2,j=0;i<=n;i++){
		while(j&&str[i]!=str[j+1]) j=fail[j];
		if(str[i]==str[j+1]) j++;
		fail[i]=j;
	}
	for(int i=0;i<=n;i++) g[i].clear();
	for(int i=1;i<=n;i++) g[fail[i]].push_back(i);
	dfs(0,0);
	for(int i=2;i<=n;i++) ans=1LL*ans*(res[i]+1)%mod;
	printf("%d\n",ans);
}
signed main(){
	v.push_back(0);
	int T; cin>>T; while(T--) solve();
	return 0;
}