AB213 F Common Prefixes 题解

题面

定义 \(f(X,Y)\) 为字符串 \(X,Y\) 的公共前缀长度。

给定长度为 \(N\) 的字符串 \(S\)，设 \(S_i\) 表示从第 \(i\) 个字符开始的 \(S\) 的后缀。

计算出：对于 \(k=1,2,...,N\),\(f(S_k,S_1)+f(S_k,S_2)+f(S_k,S_3)+...+f(S_k,S_N)\) 的值。

输入格式

第一行一个整数 \(N(1≤N≤106)\)

第二行为长度 \(N\) 的字符串 \(S\)。

输出格式

输出 \(N\) 行，第 \(k\) 行，表示 \(f(S_k,S_1)+f(S_k,S_2)+f(S_k,S_3)+...+f(S_k,S_N)\) 的值。

样例输入

3
abb

样例输出

3
3
2

样例解释

\(S1=abb,S2=bb,S3=b\)

\(For\ k=1\ f(S1,S1)+f(S1,S2)+f(S1,S3)=3+0+0=3\)

\(For\ k=2\ f(S2,S1)+f(S2,S2)+f(S2,S3)=0+2+1=3\)

\(For\ k=3\ f(S3,S1)+f(S3,S2)+f(S3,S3)=0+1+1=2\)

解题

算法：SA+LCP+单调栈

前置知识：后缀数组学习笔记

显然，\(f\) 和 \(LCP\) 的含义是相同的

我们知道，\(LCP(i,j)=\min_{i\leq k\leq j-1}\{LCP(k,k+1)\}\)

所以，问题被转化成这样：

Problem:

给定一个长为 \(n\) 的序列 \(a_i\),

令 \(g(i,j)=\min_{i\leq k\leq j-1}\{a_k\}\)

对于每一个 \(k=1\dots n\), 求值： \(\sum_{i=1}^n g(i,k)\)

我们考虑分开求，分成 \(\sum_{i=1}^{k-1}g(i,k)+g(k,k)+\sum_{i=k+1}^ng(i,k)\)

显然，第一个和第二个本质相同，中间那个就是 \(Suf(k)\) 的长度。

令 \(pre_k=\sum_{i=1}^{k-1}g(i,k)\) ,观察：

\[\begin{align} pre_k&=g(1,k)+g(2,k)+g(3,k)+\dots+g(k-1,k)\\ pre_{k+1}&=g(1,k+1)+g(2,k+1)+g(3,k+1)+\dots+g(k-1,k)+a_{k}\\ &=\min(g(1,k),a_k)+\min(g(2,k),a_k)+\dots +\min(g(k-1,k),a_k)+a_k \end{align} \]

可以发现，二者之间存在递推关系

如何处理取 \(\min\) 操作？

考虑 \(a_k\) 的贡献范围：\((前面第一个大于 a_k的位置,k+1]\)，

所以，我们可以采用 单调栈 （其实代码比文字更好懂）

另外，有一道相似的题目：[AHOI2013]差异 - 洛谷 ，其中也有单调栈的思想

代码

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

int n,m,top;
int tax[N],rk[N],sa[N],tp[N],h[N];
int pre[N],suf[N],stk[N];
char s[N];

void radix_sort(){
	for(int i=1;i<=m;++i)tax[i]=0;
	for(int i=1;i<=n;++i)tax[rk[i]]++; 
	for(int i=1;i<=m;++i)tax[i]+=tax[i-1];
	for(int i=n;i>=1;--i)sa[tax[rk[tp[i]]]--]=tp[i];
}
void suffix_sort(){
	m=75;
	for(int i=1;i<=n;++i)
		rk[i]=s[i]-'a'+1,tp[i]=i;
	radix_sort();
	for(int w=1,p=0;w<n;m=p,w<<=1,p=0){
		for(int i=1;i<=w;++i)tp[++p]=n-w+i;
		for(int i=1;i<=n;++i)if(sa[i]>w)tp[++p]=sa[i]-w;
		radix_sort();swap(tp,rk);
		rk[sa[1]]=p=1;
		for(int i=2;i<=n;++i)
			rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
	}
}
void geth(){
	int j,k=0;
	for(int i=1;i<=n;++i){
		if(k)--k;
		int j=sa[rk[i]-1];
		while(s[i+k]==s[j+k])++k;
		h[rk[i]]=k;
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;cin>>(s+1);
	suffix_sort();geth();
	stk[top=0]=1;//维护一个单调上升的栈
	for(int i=2;i<=n;++i){
		pre[i]=pre[i-1];
		while(top&&h[i]<h[stk[top]])
			pre[i]-=(stk[top]-stk[top-1])*h[stk[top--]];//减去之前的贡献
		pre[i]+=(i-stk[top])*h[i];
		stk[++top]=i;
	}
	stk[top=0]=n+1;
	for(int i=n;i>=2;--i){
		suf[i]=suf[i+1];
		while(top&&h[i]<h[stk[top]])
			suf[i]-=(stk[top-1]-stk[top])*h[stk[top--]];
		suf[i]+=(stk[top]-i)*h[i];
		stk[++top]=i;
	}
	for(int i=1;i<=n;++i)
		cout<<pre[rk[i]]+suf[rk[i]+1]+n-i+1<<"\n";
	return 0;
}