成都集训-字符串篇-JZTXT

[NOI2014]动物园

题目描述

我们给定一个字符串 $S$ ，定义 $num[i]$ 表示 $S$ 的前 $i$ 个字符组成的字符串中，长度小于等于 $\lfloor\dfrac{i}{2} \rfloor$ 的 $border$ 数量。求 $\sum (num[i]+1) $ 。

$|S| \leqslant 1e6$

思路点拨

我们考虑一个暴力，我们可以使用 $\text{KMP}$ 算法先求出 $fail$ 数组和一个 $dp$ 数组。其中 $dp_i$ 表示字符串 $S$ 的前 $i$ 个字符组成的字符串中，全部的 $border$ 的数量。这两点显然是可以线性求出的。那么，每一次我们要求出 $num[i]$ ，我们就使用一个指针 $j$ ，不断地跳 $fail_j$ 直到 $j \leqslant \lfloor \dfrac{i}{2}\rfloor$ 位置，最后 $num[i]=dp_j$ 。但是这个做法在全部都是 $a$ 的字符串中会退化成 $O(n^2)$ 。我们考虑两种优化。

倍增

因为全部的 $fail$ 数组实际上会组成一颗 $fail$ 树。我们要一直跳 $fail$ 的过程其实十分的重复，所以我们使用树上倍增的方法将其压缩至 $O(n \log n)$ 。这个做法在本题不够优秀，但是具有启发性。

基于树上倍增的进一步优化

实际上，在一般的树上上述的倍增方法已经是足够优秀了，但是这个 $fail$ 树上有更为优秀的性质。 $fail_i < i$ 。也就是说对于树上的一条链，从根到叶子的过程中，我们倍增找到的那个节点的深度是单调的。我们可以维护一个指针扫一遍。时间复杂度 $O(n)$ 。具体实现并不用那么复杂，具体看代码:

$code$

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int MAXN=1e6+10,mod=1e9+7;
int T,n,p[MAXN],f[MAXN];
string s;
signed main(){
	T=read();
	while(T--){
		cin>>s;n=s.length();
		memset(p,0,sizeof(p));
		memset(f,0,sizeof(f));
		for(int i=1;i<n;i++){
			int j=p[i];
			while(j&&s[i]!=s[j]) j=p[j];
			j+=(s[i]==s[j]);
			p[i+1]=j;
		}
		for(int i=1;i<=n;i++)
			f[i]=f[p[i]]+1;
		int ans=1,j=0;
		for(int i=1;i<n;i++){
			while(j&&s[i]!=s[j]) j=p[j];
			j+=(s[i]==s[j]);
			while(j>(i+1)/2) j=p[j];
			ans=ans*(f[j]+1)%mod; 
		}
		cout<<ans<<endl;
	}
	return 0;
}