#include<bits/stdc++.h> #define fi first #define se second #define INF 0x3f3f3f3f #define LNF 0x3f3f3f3f3f3f3f3f #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pqueue priority_queue #define NEW(a,b) memset(a,b,sizeof(a)) const double pi=4.0*atan(1.0); const double e=exp(1.0); const int maxn=4e5+8; typedef long long LL; typedef unsigned long long ULL; const LL mod=1e9+7; const ULL base=1e7+7; const int maxp=26+5; using namespace std; struct Suffix_Node{ int ch[maxp],par,len; void init(){ NEW(ch,0); par=len=0; } }; LL f[maxn];//用来求子串个数开的数组 class Suffix_Automation{ private: Suffix_Node s[maxn]; int cur,las,siz,crp; public: Suffix_Automation():las(1),cur(1),siz(1),crp(1){} const void init(){ for(int i=0;i<=siz;i++) s[i].init(); las=cur=siz=crp=1; } const int match(const char c)const{ return s[crp].ch[c-'a']; } const void withdraw(const int len){//撤掉开头几个字母，使已匹配的剩下长度为len while(crp!=0&&s[s[crp].par].len>=len) crp=s[crp].par; if(crp==0) crp=1; } const void Transfer(const int len,const char c){//匹配字符加上c保持长度为len crp=s[crp].ch[c-'a']; if(crp==0) crp=1; withdraw(len); } const void ex_tend(const char c){//扩展新字符 int x=c-'a'; cur=++siz; s[cur].len =s[las].len+1; while(las!=0&&!s[las].ch[x]) s[las].ch[x]=cur,las=s[las].par; if(las==0) s[cur].par=1; else{ int q,nq; q=s[las].ch[x]; if(s[q].len==s[las].len+1) s[cur].par=q; else{ nq=++siz; s[nq]=s[q],s[nq].len=s[las].len+1; s[cur].par=s[q].par=nq; while(las!=0&&s[las].ch[x]==q) s[las].ch[x]=nq,las=s[las].par; } } las=cur; } const int LCS(string t){//求最长公共子串 int le=0,ans=0; for(int i=0;t[i];i++){ if(match(t[i])){ le++; Transfer(le,t[i]); } else{ while(crp&&!s[crp].ch[t[i]-'a']) crp=s[crp].par; if(crp==0) le=0,crp=1; else le=s[crp].len+1,crp=s[crp].ch[t[i]-'a']; } ans=max(ans,le); } return ans; } LL getsub(){//求子串个数 return dfs(1)-1; } LL dfs(int u){ f[u]=1; for(int i=0;i<26;++i) if(s[u].ch[i]){ if(!f[s[u].ch[i]]) f[u]+=dfs(s[u].ch[i]); else f[u]+=f[s[u].ch[i]]; } return f[u]; } }SAM;
求字典序第ｋ小子串
https://www.luogu.org/problem/P3975
#include<bits/stdc++.h> #define fi first #define se second #define INF 0x3f3f3f3f #define LNF 0x3f3f3f3f3f3f3f3f #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pqueue priority_queue #define NEW(a,b) memset(a,b,sizeof(a)) #define rep(i, a, b) for(int i=(a); i<(b); i++) #define per(i, a, b) for(int i=(b)-1; i>=(a); i--) #define mem(a,x) memset(a,x,sizeof(a)) const double pi=4.0*atan(1.0); const double e=exp(1.0); const int maxn=1e6+8; typedef long long LL; typedef long long ll; typedef unsigned long long ULL; const LL mod=1e9+7; const ULL base=1e7+7; const int maxp=26+5; using namespace std; int c[maxn],a[maxn],sum[maxn],si[maxn]; struct Suffix_Node{ int ch[maxp],par,len; void init(){ NEW(ch,0); par=len=0; } }; class Suffix_Automation{ private: Suffix_Node s[maxn]; int cur,las,siz,crp; public: Suffix_Automation():las(1),cur(1),siz(1),crp(1){} const void init(){ for(int i=0;i<=siz;i++) s[i].init(); las=cur=siz=crp=1; } const int match(const char c)const{ return s[crp].ch[c-'a']; } const void withdraw(const int len){//撤掉开头几个字母，使已匹配的剩下长度为len while(crp!=0&&s[s[crp].par].len>=len) crp=s[crp].par; if(crp==0) crp=1; } const void Transfer(const int len,const char c){//匹配字符加上c保持长度为len crp=s[crp].ch[c-'a']; if(crp==0) crp=1; withdraw(len); } const void ex_tend(const char c){//扩展新字符 int x=c-'a'; cur=++siz; s[cur].len =s[las].len+1; si[cur]=1; while(las!=0&&!s[las].ch[x]) s[las].ch[x]=cur,las=s[las].par; if(las==0) s[cur].par=1; else{ int q,nq; q=s[las].ch[x]; if(s[q].len==s[las].len+1) s[cur].par=q; else{ nq=++siz; s[nq]=s[q]; s[nq].len=s[las].len+1; s[cur].par=s[q].par=nq; while(las!=0&&s[las].ch[x]==q) s[las].ch[x]=nq,las=s[las].par; } } las=cur; } const void print(int t,int k){//打印第k小子串,t为0表示不同位置的相同子串算作一个,t为1表示不同位置的相同子串算作多个 for(int i=1;i<=siz;i++) c[s[i].len]++; for(int i=1;i<=siz;i++) c[i]+=c[i-1]; for(int i=1;i<=siz;i++) a[c[s[i].len]--]=i; for(int i=siz;i;i--) if(t) si[s[a[i]].par]+=si[a[i]]; else si[a[i]]=1; si[1]=0; for(int i=siz;i;i--){ sum[a[i]]=si[a[i]]; for (int j=0;j<26;j++) if (s[a[i]].ch[j]) sum[a[i]]+=sum[s[a[i]].ch[j]]; } if(k>sum[1]){ puts("-1"); return; } int now=1; k-=si[now]; while(k>0){ int p=0; while(k>sum[s[now].ch[p]]){ k-=sum[s[now].ch[p]]; p++; } now=s[now].ch[p]; putchar('a'+p); k-=si[now]; } return; } }SAM; char s[maxn]; int main(){ int t,k; scanf("%s%d%d",s,&t,&k); SAM.init(); for(int i=0;s[i];i++){ SAM.ex_tend(s[i]); } SAM.print(t,k); }
求endpos集大小
https://cn.vjudge.net/problem/HihoCoder-1465
#include<bits/stdc++.h> #define fi first #define se second #define INF 0x3f3f3f3f #define LNF 0x3f3f3f3f3f3f3f3f #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pqueue priority_queue #define NEW(a,b) memset(a,b,sizeof(a)) #define rep(i, a, b) for(int i=(a); i<(b); i++) #define per(i, a, b) for(int i=(b)-1; i>=(a); i--) #define mem(a,x) memset(a,x,sizeof(a)) const double pi=4.0*atan(1.0); const double e=exp(1.0); const int maxn=2e6+8; typedef long long LL; typedef long long ll; typedef unsigned long long ULL; const LL mod=1e9+7; const ULL base=1e7+7; const int maxp=26+5; using namespace std; struct Suffix_Node{ int ch[maxp],par,len; int w;//用于表示endpos集大小 void init(){ NEW(ch,0); par=len=0; w=0; } }; struct node{ int to,nxt; }g[maxn]; int head[maxn],cnt; bool r[maxn]; void add(int x,int y){ g[cnt].to=y; g[cnt].nxt=head[x]; head[x]=cnt++; } class Suffix_Automation{ private: Suffix_Node s[maxn]; int cur,las,siz,crp; public: Suffix_Automation():las(1),cur(1),siz(1),crp(1){} const void init(){ for(int i=0;i<=siz;i++) s[i].init(); las=cur=siz=crp=1; } const int match(const char c)const{ return s[crp].ch[c-'a']; } const void withdraw(const int len){//撤掉开头几个字母，使已匹配的剩下长度为len while(crp!=0&&s[s[crp].par].len>=len) crp=s[crp].par; if(crp==0) crp=1; } const void Transfer(const int len,const char c){//匹配字符加上c保持长度为len crp=s[crp].ch[c-'a']; if(crp==0) crp=1; withdraw(len); } const void ex_tend(const char c){//扩展新字符 int x=c-'a'; cur=++siz; s[cur].len=s[las].len+1; s[cur].w=1; while(las!=0&&!s[las].ch[x]) s[las].ch[x]=cur,las=s[las].par; if(las==0) {s[cur].par=1;} else{ int q,nq; q=s[las].ch[x]; if(s[q].len==s[las].len+1) {s[cur].par=q;} else{ nq=++siz; s[nq]=s[q]; s[nq].w=0; s[nq].len=s[las].len+1; s[cur].par=s[q].par=nq; while(las!=0&&s[las].ch[x]==q) s[las].ch[x]=nq,las=s[las].par; } } las=cur; } int gg(){ return s[crp].w; } void dfs(int u){ r[u]=1; for(int i=head[u];i!=-1;i=g[i].nxt){ if(!r[g[i].to]) dfs(g[i].to); s[u].w+=s[g[i].to].w; } } void solve(){//求endpos集大小 for(int i=1;i<=siz;i++){ add(s[i].par,i); } for(int i=1;i<=siz;i++){ if(!r[i]) dfs(i); } } }SAM,SAM2; char s[maxn],ss[maxn]; bool vis[maxn]; int main(){ memset(head,-1,sizeof(head)); scanf("%s",s); SAM.init(); for(int i=0;s[i];i++){ SAM.ex_tend(s[i]); } SAM.solve(); int t,l; scanf("%d",&t); while(t--){ SAM2.init(); SAM.withdraw(0); scanf("%s",ss); l=strlen(ss); for(int i=l;i<2*l-1;i++){ ss[i]=ss[i-l]; } int ll=0; int ans=0; for(int i=0;i<2*l-1;i++){ while(!SAM2.match(ss[i])){ ll--; if(ll<0) break; SAM2.withdraw(ll); } SAM2.ex_tend(ss[i]); SAM2.Transfer(++ll,ss[i]); if(ll>=l) vis[i]=1; } ll=0; for(int i=0;i<2*l-1;i++){ while(!SAM.match(ss[i])){ ll++; if(ll>i) break; SAM.withdraw(i-ll); } SAM.Transfer(i-ll+1,ss[i]); if(i-ll+1>=l&&!vis[i]){ SAM.withdraw(l); ll=i+1-l; ans+=SAM.gg(); } } for(int i=0;i<2*l-1;i++){ vis[i]=0; } printf("%d ",ans); } }