command_block-SAM的应用
感谢大佬的指点
暴论：后缀数组什么辣鸡啊，再也不用后缀数组啦！加入SAM神教！
建出后缀自动机，可知一个串的出现次数即为endpos个数也是后缀链接树上的子节点个数。
同一endpos集合的子集中子串长度连续且长度区间为 \([maxlen(sam[cur].link)+1,maxlen(cur)]\) 。
两者乘起来即为答案，要开longlong
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=200010;
char s[N];
int n,cnt,du[N];
struct node{
int lin,siz,len,to[26],sumn;
}sam[N];
inline int insert(int p,int sumn){
int cur=++cnt;
sam[cur].siz=1,sam[cur].len=sam[p].len+1,sam[cur].sumn=sumn;
while(p&&!sam[p].to[sumn])sam[p].to[sumn]=cur,p=sam[p].lin;
if(!p)return sam[cur].lin=1,cur;
int q=sam[p].to[sumn];
if(sam[q].len==sam[p].len+1)return sam[cur].lin=q,cur;
int clone=++cnt;
sam[clone]=sam[q],sam[clone].len=sam[p].len+1,sam[clone].siz=0;
sam[q].lin=sam[cur].lin=clone;
while(p&&sam[p].to[sumn]==q)sam[p].to[sumn]=clone,p=sam[p].lin;
return cur;
}
void work(){
long long ans=0;
for(int i=1;i<=cnt;i++)sam[i]=sam[0],du[i]=0;
scanf("%s",s+1),n=strlen(s+1);
cnt=1;
for(int last=1,i=1;i<=n;i++)last=insert(last,s[i]-'a');
for(int i=1;i<=cnt;i++)du[sam[i].lin]++;
deque<int>que;
for(int i=1;i<=cnt;i++)if(!du[i])que.push_back(i);
while(!que.empty()){
int u=que.front();que.pop_front();
// cout<<u<<":"<<sam[u].lin<<"-"<<sam[u].len<<" "<<sam[u].siz<<"-"<<(char)(sam[u].sumn+'a')<<"\n";
ans+=1ll*(sam[u].len-sam[sam[u].lin].len)*sam[u].siz*sam[u].siz;
sam[sam[u].lin].siz+=sam[u].siz,du[sam[u].lin]--;
if(!du[sam[u].lin])que.push_back(sam[u].lin);
}
for(int i=1;i<=cnt;i++){
// cout<<i<<":"<<sam[i].lin<<"-"<<sam[i].len<<" "<<sam[i].siz<<"-"<<(char)(sam[i].sumn+'a')<<"\n";
// cout<<i<<" "<<sam[i].lin<<" "<<(char)(sam[i].sumn+'a')<<"\n";
for(int j=0;j<=25;j++){
if(!sam[i].to[j])continue;
// cout<<i<<" "<<sam[i].to[j]<<" "<<(char)(sam[j].sumn+'a')<<"\n";
}
if(!du[i])que.push_back(i);
}
printf("%lld\n",ans);
return ;
}
signed main(){
int T=rd();
while(T--)work();
return 0;
}
/*
2
llalahaffl
jijhjjhhki
*/
动态构建后缀自动机，新增的后缀就是 sam[cur].len-sam[sam[cur].link].len
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=100001;
struct node{
unordered_map<int,int>to;
int len,fro;
}sam[N*2];
int n,last,cnt;
long long ans;
void insert(int c){
int p=last,now=++cnt;
sam[now].len=sam[p].len+1;
while(p&&(!sam[p].to[c]))sam[p].to[c]=now,p=sam[p].fro;
last=now;
if(!p)return sam[now].fro=1,void(0);
if(sam[p].len+1==sam[sam[p].to[c]].len)return sam[now].fro=sam[p].to[c],void(0);
int clone=++cnt,qnode=sam[p].to[c];
sam[clone]=sam[qnode];
sam[clone].len=sam[p].len+1;
sam[qnode].fro=sam[now].fro=clone;
while(p&&sam[p].to[c]==qnode)sam[p].to[c]=clone,p=sam[p].fro;
return ;
}
signed main(){
n=rd();
last=cnt=1;
for(int i=1;i<=n;i++){
int x=rd();
insert(x);
ans+=sam[last].len-sam[sam[last].fro].len;
printf("%lld\n",ans);
}
// for(int i=1;i<=cnt;i++)cout<<i<<":"<<sam[i].len<<" "<<sam[i].fro<<"\n";
return 0;
}
很久之前写的代码，变量名可能不太一样。
- P3975 [TJOI2015]弦论
后缀自动机上DP一下。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=1000010;
char s[N];
int n,cnt=1;
int siz[N],lin[N],len[N],sum[N],to[N][26],num[N];
int t[N],A[N];
inline int insert(int p,int sumn){
int cur=++cnt;
siz[cur]=1,len[cur]=len[p]+1,num[cur]=sumn;
while(p&&!to[p][sumn])to[p][sumn]=cur,p=lin[p];
if(!p)return lin[cur]=1,cur;
int q=to[p][sumn];
if(len[p]+1==len[q])return lin[cur]=q,cur;
int clone=++cnt;
len[clone]=len[p]+1,lin[clone]=lin[q],num[clone]=num[q];
memcpy(to[clone],to[q],sizeof(to[q]));
lin[q]=lin[cur]=clone;
while(p&&to[p][sumn]==q)to[p][sumn]=clone,p=lin[p];
return cur;
}
void dfs(int u,int Sum){
Sum-=siz[u];
if(Sum<0)return ;
if(u!=1)putchar(num[u]+'a');
if(Sum<=0)return ;
for(int i=0;i<26;i++){
if(!to[u][i])continue;
if(Sum>sum[to[u][i]])Sum-=sum[to[u][i]];
else{
// cout<<u<<":"<<(char)(i+'a')<<"-"<<to[u][i]<<" "<<sum[to[u][i]]<<"-"<<Sum<<"\n";
dfs(to[u][i],Sum);
break;
}
}
return ;
}
signed main(){
scanf("%s",s+1),n=strlen(s+1);
int T=rd(),K=rd();
for(int i=1,last=1;i<=n;i++)last=insert(last,s[i]-'a');
for(int i=1;i<=cnt;i++)t[len[i]]++;
for(int i=1;i<=n;i++)t[i]+=t[i-1];
for(int i=cnt;i>=1;i--)A[t[len[i]]--]=i;
for(int i=cnt;i>=1;i--)siz[lin[A[i]]]+=siz[A[i]];
for(int i=1;i<=cnt;i++)sum[i]=(!T)?(siz[i]=1):siz[i];
sum[1]=siz[1]=0;
for(int i=cnt;i>=1;i--){
int u=A[i];
for(int j=0;j<26;j++){
if(!to[u][j])continue;
sum[u]+=sum[to[u][j]];
}
}
if(sum[1]<K)return printf("-1\n"),0;
dfs(1,K);
return 0;
}
/*
aaaaa
1 15
*/
- SP1811
SAM在类似AC机方面的作用，是把所有子串插入AC机。
但是要注意当前点的长度并不是匹配上的串的长度，但跳link之后的长度一定是匹配上的串的长度。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
struct node{
int len,lin,to[26];
}sam[N];
int n,cnt=1,ans;
char s[N];
inline int insert(int p,int sumn){
int cur=++cnt;
sam[cur].len=sam[p].len+1;
while(p&&!sam[p].to[sumn])sam[p].to[sumn]=cur,p=sam[p].lin;
if(!p)return sam[cur].lin=1,cur;
int q=sam[p].to[sumn];
if(sam[p].len+1==sam[q].len)return sam[cur].lin=q,cur;
int clone=++cnt;
sam[clone]=sam[q],sam[clone].len=sam[p].len+1;
sam[q].lin=sam[cur].lin=clone;
while(p&&sam[p].to[sumn]==q)sam[p].to[sumn]=clone,p=sam[p].lin;
return cur;
}
signed main(){
scanf("%s",s+1),n=strlen(s+1);
for(int i=1,last=1;i<=n;i++)last=insert(last,s[i]-'a');
scanf("%s",s+1),n=strlen(s+1);
for(int i=1,cur=1,len=0;i<=n;i++){
while(cur&&!sam[cur].to[s[i]-'a'])cur=sam[cur].lin,len=sam[cur].len;
if(cur)cur=sam[cur].to[s[i]-'a'],len++,ans=max(ans,len);
else cur=1,len=0;
}
printf("%d\n",ans);
return 0;
}