CSL 的密码 后缀数组 height数组应用

题目链接：点击查看

链接：https://ac.nowcoder.com/acm/contest/551/C
来源：牛客网
 

题目描述

众所周知，CSL 最喜欢的密码是 ******。于是有一天……

 

 

为了改变这一点，他决定重新设定一个密码。于是他随机生成了一个很长很长的字符串，并打算选择一个子串作为新密码。他认为安全的密码长度至少为 m，那么他有多少种不同选择方式呢？两种方案不同，当且仅当选出的密码内容不同。

输入描述:

第一行有两个整数 n 和 m ，分别表示 CSL 随机生成的字符串长度和安全的密码的最短长度。

第二行有一个长度为 n 的只含小写字母的字符串 s 表示 CSL 随机生成的字符串。

 

1≤m≤n≤1051≤m≤n≤105

输出描述:

在一行输出一个整数，表示 CSL 能选择的方案数。

示例1

输入

复制

9 1
abcabcabc

输出

复制

24

备注:

除样例外，所有的测试数据的字符串的每个字符均从小写字母 a - z 等概率随机生成。

题解：(n-m+1)*(n-m+2)/2 就是总共的数目，再把重复的去掉就可以了，height[i] 表示该字符串与前一个的公共前缀的长度，如果该长度大于等于m，就要减去一部分，即（height[i] - m + 1）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
const int N=110000;
int t1[N],t2[N],sum[N],rk[N],ht[N],sa[N],str[N],n;
char s[N];
void get_sa(int n,int m)
{
	int *x=t1,*y=t2;
	for(int i=0;i<m;i++) sum[i]=0;
	for(int i=0;i<n;i++) sum[x[i]=str[i]]++;
	for(int i=1;i<m;i++) sum[i]+=sum[i-1];
	for(int i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
	for(int p,j=1;p<=n;j<<=1)
	{
		p=0;
		for(int i=n-j;i<n;i++) y[p++]=i;
		for(int i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(int i=0;i<m;i++) sum[i]=0;
		for(int i=0;i<n;i++) sum[x[y[i]]]++;
		for(int i=1;i<m;i++) sum[i]+=sum[i-1];
		for(int i=n-1;i>=0;i--) sa[--sum[x[y[i]]]]=y[i];
		swap(x,y);
		p=1;
		x[sa[0]]=0;
		for(int i=1;i<n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
		if(p>=n) break;
		m=p;
	}
	int k=0;n--;
	for(int i=0;i<=n;i++) rk[sa[i]]=i;
	for(int i=0;i<n;i++)
	{
		if(k)k--;else k=0;
		int j=sa[rk[i]-1];
		while(str[i+k]==str[j+k])k++;
		ht[rk[i]]=k; 
	}
}
int main()
{
	int T;
	char s[100100];
	int n,m;
	scanf("%d%d",&n,&m);
	scanf("%s",s);
	n=strlen(s);
	for(int i=0;i<n;i++) str[i]=s[i];
	str[n]=0;
	get_sa(n+1,256);
	ll ans=(ll)(n-m+1)*(n-m+2)/2;
	for(int i=1;i<=n;i++)
	{
		ans-=max(0,ht[i]-m+1);	
	} 
	printf("%lld\n",ans);
	return 0;
}