• 周五. 9月 30th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

后缀数组小结?

admin

11月 28, 2021

做了一圈(就那么几道还叫一圈)$SA$的题,小结一下,方便自己看

[NOI2016]优秀的拆分

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 using namespace std;
  5 #define mem(x) memset((x),0,sizeof((x)))
  6 struct SA{
  7     char s[60005];
  8     int n,m;
  9     int t1[60005],t2[60005],t3[60005],buc[60005];
 10     int sa[60005],Rank[60005],height[60005],mn[60005][20];
 11     SA(){}
 12     inline void clear(){
 13         m=130;
 14         mem(t1),mem(t2),mem(t3),mem(buc),mem(sa),mem(Rank),mem(height),mem(mn);
 15     }
 16     inline void init(){
 17         scanf("%s",s+1);
 18         n=strlen(s+1);
 19     }
 20     inline void Suffix(){
 21         int i,j,k(0),p(0),*x(t1),*y(t2),*t;
 22         for(i=0;i<=m;++i)buc[i]=0;
 23         for(i=1;i<=n;++i)++buc[x[i]=s[i]];
 24         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
 25         for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
 26         for(j=1;p<n;j<<=1,m=p){
 27             for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
 28             for(i=1;i<=n;++i)
 29                 if(sa[i]>j)
 30                     y[++p]=sa[i]-j;
 31             for(i=0;i<=m;++i)buc[i]=0;
 32             for(i=1;i<=n;++i)t3[i]=x[y[i]];
 33             for(i=1;i<=n;++i)++buc[t3[i]];
 34             for(i=1;i<=m;++i)buc[i]+=buc[i-1];
 35             for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
 36             for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
 37                 x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
 38         }
 39         for(i=1;i<=n;++i)Rank[sa[i]]=i;
 40         for(i=1;i<=n;height[Rank[i++]]=k)
 41             for(k?--k:0,j=sa[Rank[i]-1];s[i+k]==s[j+k];++k);
 42     }
 43     inline void ST(){
 44         for(int i=1;i<=n;++i)mn[i][0]=height[i];
 45         for(int i=1;(1<<i)<=n;++i)
 46             for(int j=1;j+(1<<i)-1<=n;++j)
 47                 mn[j][i]=min(mn[j][i-1],mn[j+(1<<i-1)][i-1]);
 48     }
 49     inline int lcp(int x,int y){
 50         if(y>n)return 0;
 51         x=Rank[x],y=Rank[y];
 52         if(x>y)swap(x,y);
 53         ++x;
 54         int k(0),len(y-x+1);
 55         while((1<<k)<=len)++k;
 56         --k;
 57         return min(mn[x][k],mn[y-(1<<k)+1][k]);
 58     }
 59     inline void work(){
 60         Suffix();
 61         ST();
 62     }
 63 }a,b;
 64 inline void inv(){
 65     b.n=a.n;
 66     for(int i=1;i<=a.n;++i)
 67         b.s[i]=a.s[a.n-i+1];
 68 }
 69 typedef long long L;
 70 L ans;
 71 L cnt1[30005],cnt2[30005];
 72 inline void doit(){
 73     ans=0;
 74     mem(cnt1),mem(cnt2);
 75     int edge(a.n>>1);
 76     for(int l=1;l<=edge;++l)
 77         for(int i=l,j=l<<1;j<=a.n;i+=l,j+=l){
 78             int x(min(a.lcp(i,j),l));
 79             int y(min(b.lcp(a.n-(i-1)+1,a.n-(j-1)+1),l-1));
 80             int tmp(x+y-l+1);
 81             if(x+y>=l){
 82                 ++cnt1[i-y];--cnt1[i-y+tmp];
 83                 ++cnt2[j+x-tmp];--cnt2[j+x];
 84             }
 85         }
 86     for(int i=1;i<=a.n;++i)
 87         cnt1[i]+=cnt1[i-1],cnt2[i]+=cnt2[i-1];
 88     for(int i=1;i<=a.n;++i)
 89         ans+=cnt1[i+1]*cnt2[i];
 90     printf("%lld
",ans);
 91 }
 92 int main(){
 93     int T;
 94     scanf("%d",&T);
 95     while(T--){
 96         a.clear(),b.clear();
 97         a.init();
 98         a.work();
 99         inv();
100         b.work();
101         doit();
102     }
103 }

优秀的拆分

[Tjoi2016&Heoi2016]字符串

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 inline int read(){
 6     int sum(0);
 7     char ch(getchar());
 8     for(;ch<'0'||ch>'9';ch=getchar());
 9     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
10     return sum;
11 }
12 int n,m,q;
13 char s[100005];
14 int t1[100005],t2[100005],t3[100005],buc[100005];
15 int sa[100005],rank[100005],height[100005],mn[100005][20];
16 inline void Suffix(){
17     int i,j,k(0),p(0),*x(t1),*y(t2),*t;
18     for(i=0;i<=m;++i)buc[i]=0;
19     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
20     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
21     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
22     for(j=1;p<n;j<<=1,m=p){
23         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
24         for(i=1;i<=n;++i)
25             if(sa[i]>j)
26                 y[++p]=sa[i]-j;
27         for(i=0;i<=m;++i)buc[i]=0;
28         for(i=1;i<=n;++i)t3[i]=x[y[i]];
29         for(i=1;i<=n;++i)++buc[t3[i]];
30         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
31         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
32         for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
33             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
34     }
35     for(i=1;i<=n;++i)rank[sa[i]]=i;
36     for(i=1;i<=n;height[rank[i++]]=k)
37         for(k?--k:0,j=sa[rank[i]-1];s[i+k]==s[j+k];++k);
38 }
39 inline void ST(){
40     for(int i=1;i<=n;++i)
41         mn[i][0]=height[i];
42     for(int i=1;(1<<i)<=n;++i)
43         for(int j=1;j+(1<<i)-1<=n;++j)
44             mn[j][i]=min(mn[j][i-1],mn[j+(1<<i-1)][i-1]);
45 }
46 int cnt;
47 int rt[100005],lch[2000005],rch[2000005],sum[2000005];
48 inline void update(int &x,int las,int pos,int l,int r){
49     x=++cnt;
50 //  cout<<x<<' '<<las<<' '<<pos<<' '<<l<<' '<<r<<endl;
51     lch[x]=lch[las];
52     rch[x]=rch[las];
53     sum[x]=sum[las]+1;
54     if(l==r)
55         return;
56     int mid((l+r)>>1);
57     if(pos<=mid)
58         update(lch[x],lch[las],pos,l,mid);
59     else
60         update(rch[x],rch[las],pos,mid+1,r);
61 }
62 inline int query(int x,int y,int ll,int rr,int l,int r){
63     if(ll<=l&&r<=rr)
64         return sum[y]-sum[x];
65     int mid((l+r)>>1);
66     if(rr<=mid)
67         return query(lch[x],lch[y],ll,rr,l,mid);
68     if(mid<ll)
69         return query(rch[x],rch[y],ll,rr,mid+1,r);
70     return query(lch[x],lch[y],ll,mid,l,mid)+query(rch[x],rch[y],mid+1,rr,mid+1,r);
71 }
72 int main(){
73     n=read(),q=read(),m=130;
74     scanf("%s",s+1);
75     Suffix();
76     ST();
77     for(int i=1;i<=n;++i)
78         update(rt[i],rt[i-1],rank[i],1,n);
79     while(q--){
80         int a(read()),b(read()),c(read()),d(read());
81         int l(1),r(min(b-a+1,d-c+1)),mid,ans=0;
82         int tp(rank[c]);
83         while(l<=r){
84             mid=(l+r)>>1;
85             int tp1(tp),tp2(tp);
86             for(int i=16;i>=0;--i)
87                 if(tp1>=(1<<i)&&mn[tp1-(1<<i)+1][i]>=mid)
88                     tp1-=(1<<i);
89             for(int i=16;i>=0;--i)
90                 if(tp2+(1<<i)<=n&&mn[tp2+1][i]>=mid)
91                     tp2+=(1<<i);//cout<<l<<' '<<r<<' '<<mid<<' '<<tp1<<" "<<tp2<<endl;
92             if(query(rt[a-1],rt[b-mid+1],tp1,tp2,1,n)>0)
93                 ans=mid,l=mid+1;
94             else
95                 r=mid-1;
96         }
97         printf("%d
",ans);
98     }
99 }

字符串

[BZOJ 4310]跳蚤

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 using namespace std;
  6 char s[100005];
  7 int n,m;
  8 int t1[100005],t2[100005],t3[100005],buc[100005];
  9 int sa[100005],rank[100005],height[100005];
 10 inline void Suffix(){
 11     int i,j,k(0),p(0),*x(t1),*y(t2),*t;
 12     for(i=0;i<=m;++i)buc[i]=0;
 13     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
 14     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
 15     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
 16     for(j=1;p<n;j<<=1,m=p){
 17         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
 18         for(i=1;i<=n;++i)
 19             if(sa[i]>j)
 20                 y[++p]=sa[i]-j;
 21         for(i=0;i<=m;++i)buc[i]=0;
 22         for(i=1;i<=n;++i)t3[i]=x[y[i]];
 23         for(i=1;i<=n;++i)++buc[t3[i]];
 24         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
 25         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
 26         for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
 27             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
 28     }
 29     for(i=1;i<=n;++i)rank[sa[i]]=i;
 30     for(i=1;i<=n;height[rank[i++]]=k)
 31         for(k?--k:0,j=sa[rank[i]-1];s[i+k]==s[j+k];++k);
 32 }
 33 int k;
 34 typedef long long L;
 35 L tot;
 36 int ansl,ansr,ll,rr;
 37 /*inline void get_kth(L x){
 38     for(int i=1;i<=n;++i){
 39         if(x>(L)(n-sa[i]-height[i]+1))
 40             x-=(L)(n-sa[i]-height[i]+1);
 41         else{
 42             ll=sa[i],rr=sa[i]+height[i]+k-1;
 43             return;
 44         }
 45     }
 46 }*/
 47 inline bool cmp(int l,int r){
 48     for(int i=l,j=ll;i<=r&&j<=rr;++i,++j){
 49         if(s[i]<s[j])
 50             return true;
 51         if(s[i]>s[j])
 52             return false;
 53     }
 54 //  cout<<l<<' '<<r<<' '<<ll<<' '<<rr<<endl;
 55     if(rr-ll<r-l)
 56         return false;
 57     return true;
 58 }
 59 inline bool check(){
 60     int i,j,cnt(0);
 61     for(i=n;i>=1;i=j,++cnt){
 62         for(j=i;j>0;--j)
 63             if(!cmp(j,i))
 64                 break;
 65         if(i==j)
 66             return false;
 67     }
 68     return cnt<=k;
 69 }
 70 L sum[100005];
 71 int main(){
 72     scanf("%d%s",&k,s+1);
 73     n=strlen(s+1);
 74     m=130;
 75     Suffix();
 76     tot=n;
 77     for(int i=1;i<=n;++i){
 78         sum[i]=n-sa[i]+1-height[i];
 79         sum[i]+=sum[i-1];
 80         tot+=n-sa[i]-height[i];
 81     }
 82     L l(0),r(tot);
 83     while(l<=r){
 84         L mid((l+r)>>1);
 85 //      cout<<l<<' '<<r<<" "<<mid<<endl;
 86 //      get_kth(mid);
 87         L tmp(lower_bound(sum+1,sum+n+1,mid)-sum);
 88         ll=sa[tmp],rr=mid-sum[tmp-1]+sa[tmp]+height[tmp]-1;
 89 //      cout<<ll<<' '<<rr<<' '<<mid<<endl;
 90         if(check()){
 91             ansl=ll,ansr=rr;
 92             r=mid-1;
 93         }
 94         else
 95             l=mid+1;
 96     }
 97 //  cout<<ansl<<' '<<ansr<<endl;
 98     for(int i=ansl;i<=ansr;++i)
 99         putchar(s[i]);
100 }

跳蚤

[Sdoi2008]Sandy的卡片

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 inline int read(){
 6     int sum(0),f(1);
 7     char ch(getchar());
 8     for(;ch<'0'||ch>'9';ch=getchar())
 9         if(ch=='-')
10             f=-1;
11     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
12     return sum*f;
13 }
14 int T;
15 int len[1005],xl[1005][1005];
16 int s[105000],bl[105000],cnt;
17 int n,m;
18 int t1[105000],t2[105000],t3[105000],buc[105000];
19 int sa[105000],rank[105000],height[105000];
20 inline void Suffix(){
21     int i,j,k(0),p(0),*x(t1),*y(t2),*t;
22     for(i=0;i<=m;++i)buc[i]=0;
23     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
24     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
25     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
26     for(j=1;p<n;j<<=1,m=p){
27         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
28         for(i=1;i<=n;++i)
29             if(sa[i]>j)
30                 y[++p]=sa[i]-j;
31         for(i=0;i<=m;++i)buc[i]=0;
32         for(i=1;i<=n;++i)t3[i]=x[y[i]];
33         for(i=1;i<=n;++i)++buc[t3[i]];
34         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
35         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
36         for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
37             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
38     }
39     for(i=1;i<=n;++i)rank[sa[i]]=i;
40     for(i=1;i<=n;height[rank[i++]]=k)
41         for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];++k);
42 }
43 int l(0),r(0x7fffffff),mid,ans(0);
44 bool flag[1005];
45 inline bool check(int x){
46     int i,j,k;
47     for(i=1;i<=n;++i){
48         if(height[i]>=x){
49             for(j=i;j<=n&&height[j]>=x;++j);
50             --j;
51             memset(flag,0,sizeof(flag));
52             for(k=i-1;k<=j;++k)
53                 flag[bl[sa[k]]]=1;
54             for(k=1;k<=T&&flag[k];++k);
55             if(k==T+1)
56                 return true;
57             i=j;
58         }
59     }
60     return false;
61 }
62 int main(){
63     T=read();
64     for(int i=1;i<=T;++i){
65         len[i]=read();
66         r=min(r,len[i]);
67         for(int j=1;j<=len[i];++j){
68             xl[i][j]=read();
69             if(j!=1)
70                 m=max(xl[i][j]-xl[i][j-1],m);
71         }
72     }
73     for(int i=1;i<=T;++i){
74         for(int j=2;j<=len[i];++j){
75             s[++cnt]=xl[i][j]-xl[i][j-1];
76             bl[cnt]=i;
77         }
78         s[++cnt]=++m;
79     }
80     n=cnt;
81     Suffix();
82     while(l<=r){
83         mid=(l+r)>>1;
84         if(check(mid))
85             ans=mid,l=mid+1;
86         else
87             r=mid-1;
88     }
89     printf("%d",ans+1);
90 }

Sandy的卡片

[Usaco2007 Dec]队列变换

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 int T;
 6 char txt[2],ch[30005],s[60010];
 7 int n,m;
 8 int t1[60010],t2[60010],t3[60010],buc[60010];
 9 int sa[60010],rank[60010];
10 inline void Suffix(){
11     int i,j,p(0),*x(t1),*y(t2),*t;
12     for(i=0;i<=m;++i)buc[i]=0;
13     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
14     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
15     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
16     for(j=1;p<n;j<<=1,m=p){
17         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
18         for(i=1;i<=n;++i)
19             if(sa[i]>j)
20                 y[++p]=sa[i]-j;
21         for(i=0;i<=m;++i)buc[i]=0;
22         for(i=1;i<=n;++i)t3[i]=x[y[i]];
23         for(i=1;i<=n;++i)++buc[t3[i]];
24         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
25         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
26         for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
27             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
28     }
29     for(i=1;i<=n;++i)rank[sa[i]]=i;
30 }
31 int main(){
32     scanf("%d",&T);
33     for(int i=1;i<=T;++i){
34         scanf("%s",txt);
35         s[i]=ch[i]=txt[0];
36     }
37     s[T+1]='#';
38     for(int i=1;i<=T;++i)
39         s[T+i+1]=ch[T-i+1];
40     n=(T<<1)+1;
41     m=130;
42     Suffix();
43     int h1(1),h2(T+2);
44     while(h1-1+h2-T-2<T){//cout<<h1<<' '<<h2<<endl;
45         if(rank[h1]<rank[h2])
46             putchar(s[h1++]);
47         else
48             putchar(s[h2++]);
49         if((h1-1+h2-T-2)%80==0)
50             putchar('
');
51     }
52 }

队列变换

[BZOJ 3796]Mushroom追妹纸

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 char ch[4][150005];
  6 int len[4],bl[150005];
  7 char ran[4]={'!','@','#','$'};
  8 char s[150005];
  9 int n,m;
 10 int t1[150005],t2[150005],t3[150005],buc[150005];
 11 int sa[150005],rank[150005],height[150005];
 12 int kp[150005];
 13 bool km[150005];
 14 inline void get_kp(){
 15     kp[0]=-1;
 16     int i(0),j(-1);
 17     while(i<len[3]){
 18         while(j!=-1&&ch[3][i]!=ch[3][j])
 19             j=kp[j];
 20         kp[++i]=++j;
 21     }
 22 }
 23 inline void kmp(){
 24     int i(1),j(0);
 25     while(i<=n){
 26         while(j!=-1&&s[i]!=ch[3][j])
 27             j=kp[j];
 28         ++i,++j;
 29         if(j==len[3])
 30             km[i-len[3]]=1;
 31     }
 32 }
 33 inline void Suffix(){
 34     int i,j,k(0),p(0),*x(t1),*y(t2),*t;
 35     for(i=0;i<=m;++i)buc[i]=0;
 36     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
 37     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
 38     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
 39     for(j=1;p<n;j<<=1,m=p){
 40         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
 41         for(i=1;i<=n;++i)
 42             if(sa[i]>j)
 43                 y[++p]=sa[i]-j;
 44         for(i=0;i<=m;++i)buc[i]=0;
 45         for(i=1;i<=n;++i)t3[i]=x[y[i]];
 46         for(i=1;i<=n;++i)++buc[t3[i]];
 47         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
 48         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
 49         for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
 50             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
 51     }
 52     for(i=1;i<=n;++i)rank[sa[i]]=i;
 53     for(i=1;i<=n;height[rank[i++]]=k)
 54         for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];++k);
 55 }
 56 inline bool judge(int po,int x){//cout<<l<<' '<<r<<' '<<x<<endl;
 57     if(x<len[3])
 58         return true;
 59     for(int i=po,j=1;j<=x;++i,++j){
 60         if(km[i]&&j+len[3]-1<=x)
 61             return false;
 62     }
 63     return true;
 64 }
 65 inline bool check(int x){//cout<<x<<endl;
 66     int i,j,k;
 67     bool flag[4];
 68     for(i=1;i<=n;++i){//cout<<i<<" "<<height[i]<<endl;
 69         if(height[i]>=x){//cout<<endl;
 70             for(j=i;height[j]>=x&&j<=n;++j);
 71             --j;
 72 //          if(i==j)
 73 //              continue;
 74 //          cout<<i<<" "<<j<<endl<<endl;
 75             memset(flag,0,sizeof(flag));
 76             for(k=i-1;k<=j;++k)
 77                 flag[bl[sa[k]]]=1;
 78             if(flag[1]&&flag[2]&&judge(sa[i-1],x))
 79                 return true;
 80 //          for(k=1;flag[k]&&k<=3;++k);
 81 //          if(k==3)
 82 //              return true;
 83             i=j;
 84         }
 85     }
 86     return false;
 87 }
 88 int main(){
 89     scanf("%s%s%s",ch[1],ch[2],ch[3]);
 90     for(int i=1;i<=3;++i)
 91         len[i]=strlen(ch[i]);
 92     for(int i=1;i<=2;++i){
 93         for(int j=0;j<len[i];++j){
 94             s[++n]=ch[i][j];
 95             bl[n]=i;//cout<<n<<' '<<bl[n]<<endl;
 96         }
 97         s[++n]=ran[i];
 98     }
 99     get_kp();
100     kmp();
101     m=130;
102     Suffix();
103     int l(0),r(max(len[1],len[2])),ans(0);
104     while(l<=r){
105         int mid((l+r)>>1);
106         if(check(mid))
107             ans=mid,l=mid+1;
108         else
109             r=mid-1;
110     }
111     printf("%d",ans);
112 }

妹纸

[JSOI2007]字符加密Cipher

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 char ch[100005],s[200010];
 6 int len;
 7 int n,m;
 8 int t1[200010],t2[200010],t3[200010],buc[200010];
 9 int sa[200010],rank[200010];
10 inline void Suffix(){
11     int i,j,k(0),p(0),*x(t1),*y(t2),*t;
12     for(i=0;i<=m;++i)buc[i]=0;
13     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
14     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
15     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
16     for(j=1;p<n;j<<=1,m=p){
17         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
18         for(i=1;i<=n;++i)
19             if(sa[i]-j>0)
20                 y[++p]=sa[i]-j;
21         for(i=0;i<=m;++i)buc[i]=0;
22         for(i=1;i<=n;++i)t3[i]=x[y[i]];
23         for(i=1;i<=n;++i)++buc[t3[i]];
24         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
25         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
26         for(t=x,x=y,y=t,p=1,x[sa[1]]=1,i=2;i<=n;++i)
27             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
28     }
29     for(i=1;i<=n;++i)rank[sa[i]]=i;
30 }
31 inline char get(int x){
32     int tmp(sa[x]);//cout<<x<<" "<<tmp<<endl;
33     tmp=tmp+len-1;
34     if(tmp>n)
35         tmp-=len;
36     return s[tmp];
37 }
38 int main(){
39     scanf("%s",ch);
40     len=strlen(ch);
41     for(int i=1;i<=len;++i)
42         s[i]=ch[i-1];
43     for(int i=1;i<=len;++i)
44         s[len+i]=ch[i-1];
45     n=len<<1;
46     m=130;
47     Suffix();
48     for(int i=2;i<=n;i+=2)
49         putchar(get(i));
50 }

Cipher

还有几道$COGS$上的题,没有写博客(因为太水懒得写)

[SPOJ705]不同的子串

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 char s[50005];
 6 int n,m;
 7 int t1[50005],t2[50005],t3[50005],buc[50005];
 8 int sa[50005],rank[50005],height[50005];
 9 inline void Suffix(){
10     int i,j,k(0),p(0),*x(t1),*y(t2),*t;
11     for(i=0;i<=m;++i)buc[i]=0;
12     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
13     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
14     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
15     for(j=1;p<n;j<<=1,m=p){
16         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
17         for(i=1;i<=n;++i)
18             if(sa[i]>j)
19                 y[++p]=sa[i]-j;
20         for(i=0;i<=m;++i)buc[i]=0;
21         for(i=1;i<=n;++i)t3[i]=x[y[i]];
22         for(i=1;i<=n;++i)++buc[t3[i]];
23         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
24         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
25         for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
26             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
27     }
28     for(i=1;i<=n;++i)rank[sa[i]]=i;
29     for(i=1;i<=n;height[rank[i++]]=k)
30         for(k?--k:0,j=sa[rank[i]-1];s[i+k]==s[j+k];++k);
31 }
32 inline int gg(){
33     freopen("subst1.in","r",stdin);
34     freopen("subst1.out","w",stdout);
35     scanf("%s",s+1);
36     n=strlen(s+1);
37     m=130;
38     Suffix();
39     int ans(n);
40     for(int i=1;i<=n;++i)
41         ans+=n-height[i]-sa[i];
42     printf("%d
",ans);
43     return 0;
44 }
45 int K(gg());
46 int main(){;}

subst

乐曲主题(music theme)

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 inline int read(){
 6     int sum(0);
 7     char ch(getchar());
 8     for(;ch<'0'||ch>'9';ch=getchar());
 9     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
10     return sum;
11 }
12 int n,m;
13 int num[5005],s[5005];
14 int t1[5005],t2[5005],t3[5005],buc[5005];
15 int sa[5005],rank[5005],height[5005];
16 inline void Suffix(){
17     int i,j,k(0),p(0),*x(t1),*y(t2),*t;
18     for(i=0;i<=m;++i)buc[i]=0;
19     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
20     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
21     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
22     for(j=1;p<n;j<<=1,m=p){
23         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
24         for(i=1;i<=n;++i)
25             if(sa[i]>j)
26                 y[++p]=sa[i]-j;
27         for(i=0;i<=m;++i)buc[i]=0;
28         for(i=1;i<=n;++i)t3[i]=x[y[i]];
29         for(i=1;i<=n;++i)++buc[t3[i]];
30         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
31         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
32         for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
33             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
34     }
35     for(i=1;i<=n;++i)rank[sa[i]]=i;
36     for(i=1;i<=n;height[rank[i++]]=k)
37         for(k?--k:0,j=sa[rank[i]-1];s[i+k]==s[j+k];++k);
38 }
39 inline bool check(int x){
40     int mx(sa[1]),mn(sa[1]);
41     for(int i=2;i<=n;++i){
42         if(height[i]<x)
43             mx=mn=sa[i];
44         else{
45             mx=max(mx,sa[i]);
46             mn=min(mn,sa[i]);
47             if(mx-mn>x)
48                 return true;
49         }
50     }
51     return false;
52 }
53 inline int gg(){
54     freopen("theme.in","r",stdin);
55     freopen("theme.out","w",stdout);
56     n=read();m=190;
57     for(int i=1;i<=n;++i)
58         num[i]=read();
59     --n;
60     for(int i=1;i<=n;++i)
61         s[i]=num[i+1]-num[i]+100;
62     Suffix();
63     int l(1),r(n),mid,ans(0);
64     while(l<=r){
65         mid=(l+r)>>1;
66         if(check(mid))
67             ans=mid,l=mid+1;
68         else
69             r=mid-1;
70     }
71 //    cout<<ans<<endl;
72     if(ans>=4)
73         printf("%d",ans+1);
74     else
75         puts("0");
76 }
77 int K(gg());
78 int main(){;}

theme

[USACO Dec06]产奶的模式

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 inline int read(){
 7     int sum(0);
 8     char ch(getchar());
 9     for(;ch<'0'||ch>'9';ch=getchar());
10     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
11     return sum;
12 }
13 int n,m,k,size;
14 int num[20005],s[20005];
15 int t1[20005],t2[20005],t3[20005],buc[20005];
16 int sa[20005],rank[20005],height[20005];
17 inline void Suffix(){
18     int i,j,k(0),p(0),*x(t1),*y(t2),*t;
19     for(i=0;i<=m;++i)buc[i]=0;
20     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
21     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
22     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
23     for(j=1;p<n;j<<=1,m=p){
24         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
25         for(i=1;i<=n;++i)
26             if(sa[i]>j)
27                 y[++p]=sa[i]-j;
28         for(i=0;i<=m;++i)buc[i]=0;
29         for(i=1;i<=n;++i)t3[i]=x[y[i]];
30         for(i=1;i<=n;++i)++buc[t3[i]];
31         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
32         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
33         for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
34             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
35     }
36     for(i=1;i<=n;++i)rank[sa[i]]=i;
37     for(i=1;i<=n;height[rank[i++]]=k)
38         for(k?--k:0,j=sa[rank[i]-1];s[i+k]==s[j+k];++k);
39 }
40 inline bool check(int x){
41     int cnt(0),ans(0);
42     for(int i=1;i<=n;++i){
43         if(height[i]<x){
44             ans=max(ans,cnt);
45             cnt=0;
46         }
47         ++cnt;
48     }
49     return max(ans,cnt)>=k;
50 }
51 inline int gg(){
52     freopen("patterns.in","r",stdin);
53     freopen("patterns.out","w",stdout);
54     m=n=read(),k=read();
55     for(int i=1;i<=n;++i)
56         s[i]=num[i]=read();
57     sort(num+1,num+n+1);
58     size=unique(num+1,num+n+1)-num-1;
59     for(int i=1;i<=n;++i)
60         s[i]=lower_bound(num+1,num+size+1,s[i])-num;
61     Suffix();
62     int l(0),r(n),mid,ans(0);
63     while(l<=r){
64         mid=(l+r)>>1;
65         if(check(mid))
66             ans=mid,l=mid+1;
67         else
68             r=mid-1;
69     }
70     printf("%d",ans);
71     return 0;
72 }
73 int K(gg());
74 int main(){;}

patterns

[POJ2774]很长的信息

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 char s1[100005],s2[100005],s[200005];
 6 int len1,len2;
 7 int n,m;
 8 int bl[200005];
 9 int t1[200005],t2[200005],t3[200005],buc[200005];
10 int sa[200005],Rank[200005],height[200005];
11 inline void Suffix(){
12     int i,j,k(0),p(0),*x(t1),*y(t2),*t;
13     for(i=0;i<=m;++i)buc[i]=0;
14     for(i=1;i<=n;++i)++buc[x[i]=s[i]];
15     for(i=1;i<=m;++i)buc[i]+=buc[i-1];
16     for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
17     for(j=1;p<n;j<<=1,m=p){
18         for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
19         for(i=1;i<=n;++i)
20             if(sa[i]>j)
21                 y[++p]=sa[i]-j;
22         for(i=0;i<=m;++i)buc[i]=0;
23         for(i=1;i<=n;++i)t3[i]=x[y[i]];
24         for(i=1;i<=n;++i)++buc[t3[i]];
25         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
26         for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
27         for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
28             x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
29     }
30     for(i=1;i<=n;++i)Rank[sa[i]]=i;
31     for(i=1;i<=n;height[Rank[i++]]=k)
32         for(k?--k:0,j=sa[Rank[i]-1];s[i+k]==s[j+k];++k);
33 }
34 /*inline bool check(int x){
35     int i,j,k;
36     bool f[3];
37     for(i=1;i<=n;++i){
38         if(height[i]>=x){
39             for(j=i;height[j]>=x&&j<=n;++j);
40             --j;
41             memset(f,0,sizeof(f));
42             for(k=i-1;k<=j;++k)
43                 f[bl[sa[k]]]=1;
44             if(f[1]&&f[2])
45                 return true;
46             i=j;
47         }
48     }
49 }*/
50 int main(){
51     freopen("longlongmessage.in","r",stdin);
52     freopen("longlongmessage.out","w",stdout);
53     scanf("%s%s",s1,s2);
54     len1=strlen(s1),len2=strlen(s2);
55     for(int i=1;i<=len1;++i){
56         s[i]=s1[i-1];
57         bl[i]=1;
58     }
59     s[len1+1]='#';
60     for(int i=1;i<=len2;++i){
61         s[len1+1+i]=s2[i-1];
62         bl[i]=2;
63     }
64     n=len1+len2+1,m=130;
65 //    for(int i=1;i<=n;++i)
66 //        cout<<s[i];
67     Suffix();
68 /*    int l(0),r(min(len1,len2)),mid,ans(0);
69     while(l<=r){
70         mid=(l+r)>>1;
71         if(check(mid))
72             ans=mid,l=mid+1;
73         else
74             r=mid-1;
75     }*/
76     int ans(0);
77     for(int i=2;i<=n;++i){
78         if(sa[i]>len1+1&&sa[i-1]<len1+1)
79             ans=max(ans,height[i]);
80         if(sa[i]<len1+1&&sa[i-1]>len1+1)
81             ans=max(ans,height[i]);
82     }
83     printf("%d",ans);
84 }

longlong

然后今晚刷完这几道$SA$后,我的积分变成一个奥妙重重的数:

这是要把$22$娘和$33$娘送给我吗(雾)

不过$SA$的用法貌似还有好多,还要继续学习啊

发表回复

您的电子邮箱地址不会被公开。