传送门
samsamsam入门题。
题意简述：给出一个串让你依次插入字符，求每次插入字符之后不同子串的数量。
显然每次的变化量只跟新出现的nnn个后缀有关系，那么显然就是maxlenp−ma...
传送门
sam入门题。
题意简述：给出一个串让你依次插入字符，求每次插入字符之后不同子串的数量。
显然每次的变化量只跟新出现的n个后缀有关系，那么显然就是maxlenp−maxlenlinkp。
注意到字符集很大，可以用map来维护转移边。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=2e5+5;
int n;
typedef long long ll;
ll ans=0;
struct SAM{
int tot,last,len[N],link[N];
map<int,int>son[N];
SAM(){last=tot=1,len[0]=-1;}
inline void expand(int x){
int p=last,np=++tot;
len[last=np]=len[p]+1;
while(p&&!son[p][x])son[p][x]=np,p=link[p];
if(!p)link[np]=1;
else{
int q=son[p][x],nq;
if(len[q]==len[p]+1)link[np]=q;
else{
len[nq=++tot]=len[p]+1,son[nq]=son[q],link[nq]=link[q],link[q]=link[np]=nq;
while(p&&son[p][x]==q)son[p][x]=nq,p=link[p];
}
}
ans+=(ll)len[np]-len[link[np]];
}
}sam;
int main(){
n=read();
for(ri i=1;i<=n;++i)sam.expand(read()),cout<<ans<<\'\\n\';
return 0;
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
