#C241108C. C

标签（Label）

kmp
哈希

网址（Website）

题目详情 - C - Super

题解 - 西西弗西 - Super

题目（Problem）

题解（Solution）

方法来自 $\mathrm{DZR}$ 大佬，博客： DZhearMins 。

70分

$\qquad$暴力枚举 $i$ ，然后枚举 $len$ ，使用 $\text{Hash}$ 匹配就好了。

95分

$\qquad$容易观察到这个题目很像 $\mathrm{KMP}$ 算法，所以我们可以从这个方向想，注意到 $\mathrm{KMP}$ 的性质，我们很容易想到反转区间，然后考虑每次计算，很明显，每次我们都要找到当前位置的 $next$ 指针（也可以成为 $pi$ 指针），然后暴力判断这个指针指向的位置是否可以和当前串匹配即可。

100分

$\qquad$考虑优化，发现对于当前的一段，它的 $nxt_i$ 所代表的串和当前串是相等的，那么 $1\sim i$ 的字符串的前缀和后缀一定可以构成新的匹配，而且 $1\sim nxt_i$ 能匹配多少，当前新产生的串就可以产生多少，所以答案可以直接继承。除此之外，还有一个地方的贡献可能有贡献却被我们忽略掉了，就是 $\frac{nxt_i}{3}\sim\frac{i}{3}$ 的部分，维护好就可以了。

出题者题解

算法分析

我们可以考虑枚举 $s$ 的后缀作为 $A$。那么会贡献给所有前缀是 $AA$ 且满足长度大于 $3|A|$ 的后缀一次。

如果我们将所有后缀按照字典序排序，那么可以发现 $AA$ 前缀的后缀是一个区间，所以我们只要找到了这个区间，问题就变为了二维数点问题，用树状数组可以简单解决。

对于如何找到这个区间，我们可以二分。我们通过二分找到第一个前 $|AA|$ 个字符 $\geq AA$ 的字符串，再找到前 $|AA|$ 个字符 $> AA$ 的字符串，那么中间的左闭右开区间就是我们的目标。

上述操作中的排序、二分等过程，均需要快速查询一对后缀的 $lcp$，可以用哈希快速计算。时间复杂度 $O(n\log^2 n)$。

当然如果你会 $SA$ 那么可以把过程优化到 $O(n\log n)$。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;

const int mod = 1e9+9;
const int bas = 1331;
int hsh[N],pw[N];

int n,ans[N];
char s[N];

int pi[N][24];

void Solve(){
	scanf("%s",s+1),n=strlen(s+1);
	reverse(s+1,s+n+1);
	
	pw[0]=1;For(i,1,n) pw[i]=pw[i-1]*bas%mod;
	For(i,1,n) hsh[i] = hsh[i-1]*bas%mod+s[i];
	
	auto calc = [&](int l,int r){
		return (hsh[r]+mod-hsh[l-1]*pw[r-l+1]%mod)%mod;
	};
	
	for(int i=2,j=0;i<=n;i++){
		{//kmp 
			while(j&&s[i]!=s[j+1]) j=pi[j][0];
			if(s[j+1]==s[i]) j++;
			pi[i][0] = j;
			For(j,1,18) pi[i][j] = pi[pi[i][j-1]][j-1];
		}
		int x = i;
		for(int p=18;~p;p--){
			if(pi[x][p]*3 >= i) x=pi[x][p];
		}
		
		for(x=pi[x][0];x;x=pi[x][0]){
			if(x*3 < pi[i][0]){
				ans[i] += ans[pi[i][0]];
				break;
			}else if(calc(i-2*x+1,i-x)==hsh[x]) ans[i]++;
		}
	}Rof(i,n,1) printf("%lld%c",ans[i]," \n"[i==1]);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("ccfc.in","r",stdin);
	freopen("ccfc.out","w",stdout); 
	
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}