BZOJ3998
#include <cstdio> #include <cstring> using namespace std; int last,dis[1000011],fa[1000011],a[1000011][26],cnt,sum[1000011]; int val[1000011],n,dl[1000011],T,k; char st[1000011]; void ins(int num){ int p=last,np=last=++cnt; dis[np]=dis[p]+1;val[np]=1; while (!a[p][num]&&p) a[p][num]=np,p=fa[p]; if (!p) fa[np]=1;else{ int q=a[p][num]; if (dis[p]+1==dis[q]) fa[np]=q;else{ int nq=++cnt;dis[nq]=dis[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; while (a[p][num]==q) a[p][num]=nq,p=fa[p]; } } } void init(){ for (int i=1;i<=cnt;i++) sum[dis[i]]++; for (int i=1;i<=n;i++) sum[i+1]+=sum[i]; for (int i=cnt;i>0;i--) dl[sum[dis[i]]--]=i; for (int i=1;i<=cnt;i++) sum[i]=0; for (int i=cnt;i>0;i--){ int t=dl[i]; if (T==1) val[fa[t]]+=val[t];else val[t]=1; } val[1]=0; for (int i=cnt;i>0;i--){ int t=dl[i];sum[t]=val[t]; for (int j=0;j<26;j++) sum[t]+=sum[a[t][j]]; } } void dfs(int po,int num){ if (num<=val[po]) return; num-=val[po]; for (int i=0;i<26;i++) if (a[po][i]){ if (num<=sum[a[po][i]]){ putchar('a'+i); dfs(a[po][i],num); return; } num-=sum[a[po][i]]; } } int main(){ scanf("%s",&st); scanf("%d%d",&T,&k); last=cnt=1;dis[1]=1;n=strlen(st); for (int i=0;i<n;i++) ins(st[i]-'a'); init(); if (k>sum[1]) printf("-1 ");else dfs(1,k); }
-------------------------------------------
BZOJ2806
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int last,cnt,dis[3000001],a[3000001][3],fa[3000001],mat[3000001]; int dp[3000001]; char st[3000001]; void insert(int num){ int p=last,np=last=++cnt; dis[np]=dis[p]+1; while (!a[p][num]&&p) a[p][num]=np,p=fa[p]; if (!p) fa[np]=1;else{ int q=a[p][num]; if (dis[p]+1==dis[q]) fa[np]=q;else{ int nq=++cnt;dis[nq]=dis[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; while (a[p][num]==q) a[p][num]=nq,p=fa[p]; } } } void pre(int len){ int po=1,cnt=0; for (int i=1;i<=len;i++){ int num=st[i]-'0'; if (a[po][num]) cnt++,po=a[po][num];else{ while (po&&!a[po][num]) po=fa[po]; if (po) cnt=dis[po]+1,po=a[po][num];else cnt=0,po=1; } mat[i]=cnt; } }//以任意位置结尾的最长匹配长度 struct dddl{ int top,but,num[1000001],pos[1000001]; void push(int po,int nu){ while (top>=but&&nu>=num[top]) top--; top++;num[top]=nu;pos[top]=po; } void pop(int po){ while (top>=but&&pos[but]<po) but++; } int get(){ return(num[but]); } }dl; int check(int mid,int len){ for (int i=0;i<=len;i++) dp[i]=0; dl.top=0;dl.but=1; for (int i=1;i<=len;i++){ dp[i]=dp[i-1]; if (i>=mid) dl.push(i-mid,dp[i-mid]-(i-mid)); dl.pop(i-mat[i]); if (dl.top>=dl.but) dp[i]=max(dl.get()+i,dp[i]); } if (dp[len]*10>=len*9) return(1);else return(0); } int main(){ int n,m; scanf("%d%d",&n,&m); cnt=1;last=1; for (int i=1;i<=m;i++){ scanf("%s",&st); int t=strlen(st); for (int j=0;j<t;j++) insert(st[j]-'0'); insert(2); } while (n--){ scanf("%s",st+1); int len=strlen(st+1); pre(len); int l=1,r=len; while (l<r){ int mid=(l+r+1)>>1; if (check(mid,len)) l=mid;else r=mid-1; } if (check(l,len)) printf("%d ",l);else printf("0 "); } }
——————————————————————
BZOJ4032
#include <cstdio> #include <cstring> using namespace std; int vis[4001][4001],dl[16000001][3],head,tail; char A[4001],B[4001]; struct automaton{ int last,cnt,dis[4001],fa[4001],a[4001][26]; void insert(int num){ int p=last,np=last=++cnt; dis[np]=dis[p]+1; while (p&&!a[p][num]) a[p][num]=np,p=fa[p]; if (!p) fa[np]=1;else{ int q=a[p][num]; if (dis[q]==dis[p]+1) fa[np]=q;else{ int nq=++cnt;dis[nq]=dis[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; while (a[p][num]==q) a[p][num]=nq,p=fa[p]; } } } void build1(char st[]){ int n=strlen(st+1); cnt=1;last=1; for (int i=1;i<=n;i++) insert(st[i]-'a'); } void build2(char st[]){ int n=strlen(st+1);cnt=n+1; for (int i=n;i>=1;i--){ memcpy(a[i],a[i+1],sizeof(a[i+1])); a[i][st[i]-'a']=i+1; } } }a1,a2,b1,b2; void bfs(automaton &a,automaton &b){ for (int i=1;i<=a.cnt;i++) for (int j=1;j<=b.cnt;j++) vis[i][j]=0; vis[1][1]=1; dl[head=tail=1][0]=1;dl[1][1]=1;dl[1][2]=0; while (head<=tail){ for (int i=0;i<26;i++){ int t1=a.a[dl[head][0]][i],t2=b.a[dl[head][1]][i]; if (t1&&!t2) {printf("%d ",dl[head][2]+1);return;} if (t1&&t2&&!vis[t1][t2]){ tail++; dl[tail][0]=t1;dl[tail][1]=t2;dl[tail][2]=dl[head][2]+1; vis[t1][t2]=1; } } head++; } } int main(){ scanf("%s",A+1);scanf("%s",B+1); a1.build1(A);a2.build2(A); b1.build1(B);b2.build2(B); bfs(a1,b1); bfs(a1,b2); bfs(a2,b1); bfs(a2,b2); }