Lexicographical Substring SearchGlass BeadsReincarnationstr2intCommon SubstringsAB StringNew Distinct SubstringsBoring counting

Lexicographical Substring Search

给一个字符串，求第k大子串，经典题

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (180000+10) #define Sigmasize (26) typedef unsigned long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} class SAM { public: char s[MAXN]; int n; SAM():n(0){MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} SAM(char *_s){n=strlen(_s),memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(){n=0; MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(char *_s){n=strlen(_s);memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0; MEMI(l) MEMi(r) MEM(c) MEM(q)} int son[MAXN][Sigmasize+1],pre[MAXN],step[MAXN],last,tot; int l[MAXN],r[MAXN]; void extend(char ch) { step[++tot]=step[last]+1; int p=last,np=tot; l[tot]=r[tot]=step[tot]; for(;!son[p][ch];p=pre[p]) son[p][ch]=np; if (!p) pre[np]=1; else { int q=son[p][ch]; if (step[q]==step[p]+1) pre[np]=q; else { step[++tot]=step[p]+1; int nq=tot; memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; } } last=np; } void build(){ last=tot=1; Rep(i,n) extend(s[i]-'a'); } int c[MAXN],q[MAXN],len[MAXN],sz[MAXN]; void calc() { MEM(c) For(i,tot) c[step[i]]++; For(i,tot) c[i]+=c[i-1]; For(i,tot) q[c[step[i]]--]=i; ForD(i,tot) { int u=q[i]; l[pre[u]]=min(l[pre[u]],l[u]); r[pre[u]]=max(r[pre[u]],r[u]); sz[u]=1; Rep(c,26) if (son[u][c]) { sz[u]+=sz[son[u][c]]; } } } void dfs(int x,int k) { if (k==1) return; k--; Rep(c,26) if (son[x][c]) { if (sz[son[x][c]]>=k) { putchar(c+'a'); dfs(son[x][c],k); return; } else k-=sz[son[x][c]]; } } }S1; char s[MAXN]; int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int main() { // freopen("D.in","r",stdin); scanf("%s",s); int n=strlen(s); S1.mem(s); S1.build(); S1.calc(); int q=read(); while(q--) { S1.dfs(1,1+read()); puts(""); } return 0; }

Glass Beads

求最小循环串

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (40000+10) #define Sigmasize (26) typedef unsigned long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} class SAM { public: char s[MAXN]; int n; SAM():n(0){MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} SAM(char *_s){n=strlen(_s),memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(){n=0; MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(char *_s){n=strlen(_s);memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0; MEMI(l) MEMi(r) MEM(c) MEM(q)} int son[MAXN][Sigmasize+1],pre[MAXN],step[MAXN],last,tot; int l[MAXN],r[MAXN]; void extend(char ch) { step[++tot]=step[last]+1; int p=last,np=tot; l[tot]=r[tot]=step[tot]; for(;!son[p][ch];p=pre[p]) son[p][ch]=np; if (!p) pre[np]=1; else { int q=son[p][ch]; if (step[q]==step[p]+1) pre[np]=q; else { step[++tot]=step[p]+1; int nq=tot; memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; } } last=np; } void build(){ last=tot=1; Rep(i,n) extend(s[i]-'a'); } int c[MAXN],q[MAXN],len[MAXN]; void calc() { MEM(c) For(i,tot) c[step[i]]++; For(i,tot) c[i]+=c[i-1]; For(i,tot) q[c[step[i]]--]=i; ForD(i,tot) { int u=q[i]; l[pre[u]]=min(l[pre[u]],l[u]); r[pre[u]]=max(r[pre[u]],r[u]); } MEM(len) For(i,tot) { len[i]=step[i]-step[pre[i]]; } } int dfs(int x,int len) { For(i,len) { Rep(c,26) if (son[x][c]) { x=son[x][c]; break; } } return l[x]; } }S1; char s[MAXN]; int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int main() { freopen("H.in","r",stdin); int T=read(); while(T--) { scanf("%s",s); int n=strlen(s); strncpy(s+n,s,n); s[2*n]=0; S1.mem(s); S1.build(); S1.calc(); printf("%d\n",S1.dfs(1,n)+1-n); } return 0; }

Reincarnation

给出一个字符串，最长2000，q个询问，每次询问[l,r]区间内有多少个不同的字串。 转自：http://www.tuicool.com/articles/Mjuu2y SAM 中的每个状态能够表示的不同子串的个数为 val - 父结点的 val。因此在构造自动机时，用变量 total 记录当前自动机能够表示的不同子串数，对每一次 extend 都更新 total 的值。将这个过程中的每一个 total 值都记录下了就能得到一个表示子串个数表。我们对字符串的每一个后缀都重新构造一遍 SAM 就可以得到一个二维的表。

对每次询问，在表中查找相应的值即可。

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (4000+10) #define Sigmasize (26) typedef unsigned long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int f[MAXN][MAXN]; class SAM { public: char s[MAXN]; int n; SAM():n(0){MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} SAM(char *_s){n=strlen(_s),memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(){n=0; MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(char *_s){n=strlen(_s);memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0;} int son[MAXN][Sigmasize+1],pre[MAXN],step[MAXN],last,tot; void extend(char ch) { step[++tot]=step[last]+1; int p=last,np=tot; for(;!son[p][ch];p=pre[p]) son[p][ch]=np; if (!p) pre[np]=1; else { int q=son[p][ch]; if (step[q]==step[p]+1) pre[np]=q; else { step[++tot]=step[p]+1; int nq=tot; memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; } } last=np; } void build(int he){ last=tot=1; Rep(i,n) { extend(s[i]-'a'); if (!i) f[he][he+i]=1; else f[he][he+i]=f[he][he+i-1]+step[last]-step[pre[last]]; } } }S1; char s[MAXN]; int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int main() { // freopen("J.in","r",stdin); int T=read(); while(T--) { scanf("%s",s); int n=strlen(s); Rep(i,n) { S1.mem(s+i); S1.build(i); } int q=read(); while(q--) { int l=read()-1,r=read()-1; printf("%d\n",f[l][r]); } } return 0; }

str2int

给出n个数字，数字很长，用字符串读入，长度总和为10^5。求这n个字符串的所有子串（不重复）的和取模2012 。 转自：http://www.tuicool.com/articles/Mjuu2y 设父结点为 u 向数字 k 移动到的子结点为 v， 显然结点 v 的状态要在 sum 上增加 add=u->sum*10+u->cnt*k。即 u 的能表示的数字总和乘上10再加上到达 v 的方法总数乘上当前的个位数字 k。

#include<bits/stdc++.h> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (100000*2+10000*2+10) #define Sigmasize (10) typedef unsigned long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} class SAM { public: char s[MAXN]; int n; SAM():n(0){MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} SAM(char *_s){n=strlen(_s),memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(){n=0; MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(char *_s){n=strlen(_s);memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0; MEMI(l) MEMi(r) } int son[MAXN][Sigmasize+1],pre[MAXN],step[MAXN],last,tot; int l[MAXN],r[MAXN]; void extend(char ch) { step[++tot]=step[last]+1; int p=last,np=tot; l[tot]=r[tot]=step[tot]; for(;!son[p][ch];p=pre[p]) son[p][ch]=np; if (!p) pre[np]=1; else { int q=son[p][ch]; if (step[q]==step[p]+1) pre[np]=q; else { step[++tot]=step[p]+1; int nq=tot; memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; } } last=np; } void build(){ last=tot=1; Rep(i,n) extend(s[i]-'0'); } int c[MAXN],q[MAXN]; int sum[MAXN],cnt[MAXN]; void calc() { MEM(c) For(i,tot) c[step[i]]++; For(i,tot) c[i]+=c[i-1]; For(i,tot) q[c[step[i]]--]=i; MEM(sum) MEM(cnt) cnt[1]=1; For(i,tot) { int u=q[i]; Rep(c,10) if (son[u][c]){ if (i==1&&c==0) continue; int v=son[u][c]; cnt[v]+=cnt[u]; sum[v]+=sum[u]*10+cnt[u]*c; sum[v]%=2012; } } ll ans=0; For(i,tot) ans=(ans+sum[i])%2012; cout<<ans<<endl; } }S1; int n; char s[MAXN]; int main() { // freopen("K.in","r",stdin); while(cin>>n) { int p=0; Rep(i,n) { scanf("%s",s+p); p+=strlen(s+p); s[p++]='9'+1; } s[p]=0; S1.mem(s); S1.build(); S1.calc(); } return 0; }

Common Substrings

A substring of a string T is defined as:

T( i, k)= TiTi +1… Ti+k -1, 1≤ i≤ i+k-1≤| T|. Given two strings A, B and one integer K, we define S, a set of triples (i, j, k):

S = {( i, j, k) | k≥ K, A( i, k)= B( j, k)}. You are to give the value of |S| for specific A, B and K.

直接匹配不行，还要向父节点走一遍，所以我们打个标记，上传

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (111111*2+10) #define Sigmasize (26*2) typedef unsigned long long ll; int K; class SAM { public: char s[MAXN]; int n; void mem(char *_s){ n=strlen(_s); memcpy(s,_s,sizeof(char)*(n+5)); Rep(i,2*n+2) { Rep(j,Sigmasize) son[i][j]=0; pre[i]=step[i]=cnt[i]=c[i]=mark[i]=0; } last=tot=0; } int son[MAXN][Sigmasize+1],pre[MAXN],step[MAXN],last,tot; void extend(char ch) { step[++tot]=step[last]+1; int p=last,np=tot; for(;!son[p][ch];p=pre[p]) son[p][ch]=np; if (!p) pre[np]=1; else { int q=son[p][ch]; if (step[q]==step[p]+1) pre[np]=q; else { step[++tot]=step[p]+1; int nq=tot; memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; } } last=np; cnt[last]++; } int id(char c) { return c-((islower(c))?'a':'A'-26); } void build(){ last=tot=1; Rep(i,n) extend(id(s[i])); } int c[MAXN],q[MAXN],cnt[MAXN]; void calc() { For(i,tot) c[step[i]]++; For(i,tot) c[i]+=c[i-1]; For(i,tot) q[c[step[i]]--]=i; ForD(i,tot) { int u=q[i]; cnt[pre[u]]+=cnt[u]; } } ll mark[MAXN]; void dp(char *s) { int t=0,p=0; int n=strlen(s); ll ans=0; Rep(i,n) { int ch=id(s[i]); if (son[t][ch]) p++,t=son[t][ch]; else { while (t && !son[t][ch]) { t=pre[t]; p=step[t]; } if (!t) t=1,p=0; else { p=step[t]+1; t=son[t][ch]; } } if (p>=K) { ans+=(ll)max(0,min(step[t],p)-max(K-1,step[pre[t]] ) ) * cnt[t]; } if (step[pre[t]]>=K) mark[pre[t]]++; } ForD(i,tot){ int u=q[i]; if (mark[u]) ans+=(ll)mark[u]*cnt[u] * max(0,(step[u]-max(K-1,step[pre[u]]))); if (step[pre[u]]>=K) mark[pre[u]]+=mark[u]; } printf("%lld\n",ans); } }S1; char s[MAXN]; int main() { // freopen("L.in","r",stdin); while(scanf("%d",&K)&&K) { scanf("%s",s); S1.mem(s); S1.build(); scanf("%s",s); S1.calc(); S1.dp(s); } return 0; }

AB String

求第k大没出现的字符串，

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (40000+10) #define Sigmasize (2) typedef unsigned long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} class SAM { public: char s[MAXN]; int n; SAM():n(0){MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} SAM(char *_s){n=strlen(_s),memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(){n=0; MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(char *_s){n=strlen(_s);memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0; MEMI(l) MEMi(r) MEM(c) MEM(q)} int son[MAXN][Sigmasize+1],pre[MAXN],step[MAXN],last,tot; int l[MAXN],r[MAXN]; void extend(char ch) { step[++tot]=step[last]+1; int p=last,np=tot; l[tot]=r[tot]=step[tot]; for(;!son[p][ch];p=pre[p]) son[p][ch]=np; if (!p) pre[np]=1; else { int q=son[p][ch]; if (step[q]==step[p]+1) pre[np]=q; else { step[++tot]=step[p]+1; int nq=tot; memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; } } last=np; } void build(){ last=tot=1; Rep(i,n) extend(s[i]-'A'); } int c[MAXN],q[MAXN],len[MAXN],sz[MAXN]; void calc() { MEM(c) For(i,tot) c[step[i]]++; For(i,tot) c[i]+=c[i-1]; For(i,tot) q[c[step[i]]--]=i; ForD(i,tot) { int u=q[i]; l[pre[u]]=min(l[pre[u]],l[u]); r[pre[u]]=max(r[pre[u]],r[u]); sz[u]=1; Rep(c,Sigmasize) if (son[u][c]) { sz[u]+=sz[son[u][c]]; } } } int dfs(int x,int len) { if(!len) return 0; int ans=0; Rep(c,Sigmasize) if (son[x][c]) { ans+=dfs(son[x][c],len-1); } else ans+=1<<len-1; return ans; } char st[MAXN]; int dfs(int x,int k,int len,int l) { if(!len) return 0; int ans=0; Rep(c,Sigmasize) { st[l]=c+'A'; if (son[x][c]) { int p=dfs(son[x][c],k,len-1,l+1); ans+=p; if (p>=k) { return ans; } k-=p; } else { int p=1<<len-1; ans+=p; if (p>=k) { Rep(i,l) putchar(st[i]); putchar(st[l]); len--; while(len) { if ((1<<len-1)>=k) putchar('A'); else { k-=1<<len-1; putchar('B'); } --len; } return ans; } k-=p; } } return ans; } }S1; char s[MAXN]; int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int main() { // freopen("O.in","r",stdin); int T=read(); while(T--) { scanf("%s",s); int n=strlen(s); S1.mem(s); S1.build(); S1.calc(); int q=read(); while(q--) { int k=read(); for(int len=1;;len++) { int sz=S1.dfs(1,len); if (k>sz) k-=sz; else { S1.dfs(1,k,len,0); puts(""); break; } } } } return 0; }

New Distinct Substrings

字符串本质不同子串数

#include<bits/stdc++.h> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (90000*2+10) #define Sigmasize (26) typedef unsigned long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} class SAM { public: char s[MAXN]; int n; SAM():n(0){MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} SAM(char *_s){n=strlen(_s),memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(){n=0; MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(char *_s){n=strlen(_s);memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0; } int son[MAXN][Sigmasize+1],pre[MAXN],step[MAXN],last,tot; void extend(char ch) { step[++tot]=step[last]+1; int p=last,np=tot; for(;!son[p][ch];p=pre[p]) son[p][ch]=np; if (!p) pre[np]=1; else { int q=son[p][ch]; if (step[q]==step[p]+1) pre[np]=q; else { step[++tot]=step[p]+1; int nq=tot; memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; } } last=np; } void build(){ last=tot=1; Rep(i,n) extend(s[i]-'a'); } ll calc() { ll ans=0; For(i,tot) { ans+=max(0,step[i]-step[pre[i]]); } cout<<ans<<endl; } }S1; char s[MAXN]; int main() { // freopen("U.in","r",stdin); int T;cin>>T; while(T--) { scanf("%s",s); S1.mem(s); S1.build(); ll tot=0; S1.calc(); } return 0; }

Boring counting

一个字符串有多少子串，出现了至少两次且不重叠 eg：ababa aba[1.3]和aba[3.5]重叠,所以不算,ab[1.2]和ab[3.4]算 后缀自动机上每个节点的所以后缀right集合相同(right集合就是后缀出现的位置，比如ababa中aba的right视为(3,5)),所以只要计算出可能后缀的长度，出现的最左最右的位置，就行了

#include<bits/stdc++.h> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (90000+10) #define Sigmasize (26) typedef unsigned long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} class SAM { public: char s[MAXN]; int n; SAM():n(0){MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} SAM(char *_s){n=strlen(_s),memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(){n=0; MEM(s) MEM(son) MEM(pre) MEM(step) last=tot=0;} void mem(char *_s){n=strlen(_s);memcpy(s,_s,sizeof(char)*(n+5)); MEM(son) MEM(pre) MEM(step) last=tot=0; MEMI(l) MEMi(r) } int son[MAXN][Sigmasize+1],pre[MAXN],step[MAXN],last,tot; int l[MAXN],r[MAXN]; void extend(char ch) { step[++tot]=step[last]+1; int p=last,np=tot; l[tot]=r[tot]=step[tot]; for(;!son[p][ch];p=pre[p]) son[p][ch]=np; if (!p) pre[np]=1; else { int q=son[p][ch]; if (step[q]==step[p]+1) pre[np]=q; else { step[++tot]=step[p]+1; int nq=tot; memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; } } last=np; } void build(){ last=tot=1; Rep(i,n) extend(s[i]-'a'); } int c[MAXN],q[MAXN]; void calc() { MEM(c) For(i,tot) c[step[i]]++; For(i,tot) c[i]+=c[i-1]; For(i,tot) q[c[step[i]]--]=i; ForD(i,tot) { int u=q[i]; l[pre[u]]=min(l[pre[u]],l[u]); r[pre[u]]=max(r[pre[u]],r[u]); } ll ans=0; For(i,tot) ans+=max(0,min(r[i]-l[i],step[i])-step[pre[i]] ); cout<<ans<<endl; } }S1; char s[MAXN]; int main() { // freopen("V.in","r",stdin); while(1) { scanf("%s",s); if (strcmp(s,"#")==0) return 0; S1.mem(s); S1.build(); S1.calc(); } return 0; }