后缀数组

做个专题，好好研究一下；

1.[后缀数组预备知识]基数排序

/*chad*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<string>
using namespace std;
const int maxn(100010),inf(1000000000);
#define FILE "dealing"
#define LL long long
#define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)
namespace IO{
    char buf[1<<15],*fs,*ft;
    int gc(){return (fs==ft&&((ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft))?-1:*fs++;}
    LL read(){
        LL x=0,ch=gc(),f=0;
        while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();}
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
        return f?-x:x;
    }
}using namespace IO;
int n;
char s[maxn][12];
int c[maxn],m=130,x[maxn],sa[maxn],y[maxn];
int main(){
    scanf("%d",&n);
    up(i,1,n)scanf("%s",s[i]);
    for(int i=1;i<=n;i++)y[i]=i;
    for(int k=9;k>=0;k--){
        for(int i=0;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)c[s[i][k]]++;
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[s[y[i]][k]]--]=y[i];//sa[i]表示sa[i]个字符串在第i位
                for(int i=1;i<=n;i++)
            y[i]=sa[i];
    }
    up(i,1,n)printf("%d ",sa[i]);
    return 0;
}

View Code

2.[后缀数组]基因突变

最近，jzyz的科学家忽然发现了一种神秘的生物出现在了霞栖湖中，通过提取DNA，科学家发现这个生物的DNA由a.....z共26种碱基对组成，而且这个生物常常容易发生DNA片段的缺失。那么问题来了。科学家想知道DNA片段的缺失对这个生物会产生什么影响。

给你一段长为N的DNA序列（保证全为小写字母），请求出从x到y-1的片段缺失后，忽略前x-1的长度，他们最长还有多长连续序列是相同的？

这题的主要难度在于读懂题目；

实质是求lcp；

 1 /*chad*/
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<cstring>
 7 #include<algorithm>
 8 using namespace std;
 9 const int maxn(300005),inf(100000000);
10 #define FILE "dealing"
11 #define LL long long
12 #define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)
13 namespace IO{
14     char buf[1<<15],*fs,*ft;
15     int gc(){return (fs==ft&&((ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft))?-1:*fs++;}
16     int read(){
17         int x=0,ch=gc(),f=0;
18         while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();}
19         while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
20         return f?-x:x;
21     }
22 }using namespace IO;
23 char s[maxn];
24 int n,limit;
25 int t1[maxn],t2[maxn],c[maxn],sa[maxn];
26 void getsa(int m){
27     int *x=t1,*y=t2;
28     for(int i=0;i<m;i++)c[i]=0;
29     for(int i=0;i<n;i++)c[x[i]=s[i]]++;
30     for(int i=1;i<m;i++)c[i]+=c[i-1];
31     for(int i=n-1;i>=0;i--)
32         sa[--c[x[i]]]=i;
33     for(int k=1,p=0;k<=n;k<<=1){
34         p=0;
35         for(int i=n-k;i<n;i++)y[p++]=i;
36         for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
37         for(int i=0;i<m;i++)c[i]=0;
38         for(int i=0;i<n;i++)c[x[y[i]]]++;
39         for(int i=0;i<m;i++)c[i]+=c[i-1];
40         for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
41         swap(x,y);
42         x[sa[0]]=0;p=1;
43         for(int i=1;i<n;i++)
44             x[sa[i]]= (y[sa[i]]==y[sa[i-1]]&&y[sa[i-1]+k]==y[sa[i]+k])?p-1:p++;
45         if(p>=n)break;
46         m=p;
47     }
48 }
49 int rank[maxn],height[maxn];
50 void getheight(){
51     int i,j,k=0;
52     for(i=0;i<n;i++)rank[sa[i]]=i;
53     for(i=0;i<n;i++){
54         if(k)k--;
55         if(rank[i]-1<0)continue;
56         j=sa[rank[i]-1];
57         while(s[j+k]==s[i+k])k++;
58         height[rank[i]]=k;
59     }
60 }
61 int d[maxn][30];
62 int main(){
63     //freopen("dealing.in","r",stdin);
64     //freopen("dealing.out","w",stdout);
65     scanf("%d",&n);n++;limit=(int)log2(n*1.0+1)+1;
66     scanf("%s",s);
67     int q,x,y;
68     scanf("%d",&q);
69     getsa(300);
70     getheight();
71     memset(d,10,sizeof(d));
72     for(int i=0;i<n;i++)d[i][0]=height[i+1];
73     for(int j=1;j<=limit;j++)
74         for(int i=0;i<n;i++)
75             if(i+(1<<j-1)<n)d[i][j]=min(d[i][j-1],d[i+(1<<j-1)][j-1]);
76     while(q--){
77         scanf("%d%d",&x,&y);
78         if(x==y){printf("%d
",n-x);continue;}
79         x=rank[x-1],y=rank[y-1];
80         if(x>y)swap(x,y);
81         int ans=inf;
82         for(int i=limit;i>=0;i--)
83             if(x+(1<<i)<=y)ans=min(ans,d[x][i]),x=x+(1<<i);
84         printf("%d
",ans);
85     }
86     return 0;
87 }

View Code

第三次世界大战爆发期间，美德两军同盟，为了传递军事机密，两方约定以相关的秘钥进行密文的破译，尽管这样，他们仍然担心情报的安全性，于是约定对于一段密文，只有密文中最长重复的片段是有效且可翻译的情报（最长的重复片段可以重叠），例如对于这样一段长度N=5的密文：ababa，只有aba是有效密文，他们需要设计一个程序来找到这一段有效密文。

为了方便对比，只输出找出最长子串的长度即可。

对于同一个字符串来说，height数组里的max值即为答案；

 1 /*chad*/
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<ctime>
 9 #include<string>
10 using namespace std;
11 const int maxn(100010),inf(1000000000);
12 #define FILE "dealing"
13 #define LL long long
14 #define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)
15 namespace IO{
16     char buf[1<<15],*fs,*ft;
17     LL gc(){return (fs==ft&&((ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft))?-1:*fs++;}
18     LL read(){
19         LL x=0,ch=gc(),f=0;
20         while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();}
21         while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
22         return f?-x:x;
23     }
24 }using namespace IO;
25 int n;
26 char s[maxn];
27 int t1[maxn],t2[maxn],c[maxn],rank[maxn],height[maxn],sa[maxn];
28 void getsa(int m){
29     int *x=t1,*y=t2;
30     for(int i=0;i<m;i++)c[i]=0;
31     for(int i=0;i<n;i++)c[x[i]=s[i]]++;
32     for(int i=1;i<m;i++)c[i]+=c[i-1];
33     for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
34     for(int k=1,p;k<=n;k<<=1){
35         p=0;
36         for(int i=n-k;i<n;i++)y[p++]=i;
37         for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
38         for(int i=0;i<m;i++)c[i]=0;
39         for(int i=0;i<n;i++)c[x[y[i]]]++;
40         for(int i=1;i<m;i++)c[i]+=c[i-1];
41         for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
42         swap(x,y);
43         x[sa[0]]=0;p=1;
44         for(int i=1;i<n;i++)
45             x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i-1]+k]==y[sa[i]+k])?p-1:p++;
46         if(p>=n)break;
47         m=p;
48     }
49 }
50 void getheight(){
51     int i,j,k=0;
52     for(int i=0;i<n;i++)rank[sa[i]]=i;
53     for(int i=0;i<n;i++){
54         if(k)k--;
55         if(rank[i]-1<0)continue;
56         j=sa[rank[i]-1];
57         while(s[j+k]==s[i+k])k++;
58         height[rank[i]]=k;
59     }
60 }
61 int main(){
62     scanf("%d",&n);n++;
63     scanf("%s",s);
64     getsa(300);
65     getheight();
66     int ans=0;
67     for(int i=1;i<n;i++)ans=max(height[i],ans);
68     cout<<ans<<endl;
69     return 0;
70 }

View Code

4.可重叠的最少重复k次的最长子串

二分一下最长长度，再判断一下是否重复k次以上即可；

 1 /*chad*/
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<ctime>
 9 #include<string>
10 using namespace std;
11 const int maxn(1000010),inf(1000000000);
12 #define FILE "dealing"
13 #define LL long long
14 #define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)
15 namespace IO{
16     char buf[1<<15],*fs,*ft;
17     LL gc(){return (fs==ft&&((ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft))?-1:*fs++;}
18     LL read(){
19         LL x=0,ch=gc(),f=0;
20         while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();}
21         while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
22         return f?-x:x;
23     }
24 }using namespace IO;
25 int n,k;
26 int s[maxn],c[maxn],rank[maxn],height[maxn],t1[maxn],t2[maxn],sa[maxn];
27 bool chkmax(int &a,int b){return a<b?(a=b,true):false;}
28 void getsa(int m){
29     int *x=t1,*y=t2;
30     for(int i=0;i<m;i++)c[i]=0;
31     for(int i=0;i<n;i++)c[x[i]=s[i]]++;
32     for(int i=1;i<m;i++)c[i]+=c[i-1];
33     for(int i=0;i<n;i++)sa[--c[x[i]]]=i;
34     for(int k=1,p;k<=n;k<<=1){
35         p=0;
36         for(int i=n-k;i<n;i++)y[p++]=i;
37         for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
38         for(int i=0;i<m;i++)c[i]=0;
39         for(int i=0;i<n;i++)c[x[y[i]]]++;
40         for(int i=1;i<m;i++)c[i]+=c[i-1];
41         for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
42         swap(x,y);
43         x[sa[0]]=0;p=1;
44         for(int i=1;i<n;i++)
45             x[sa[i]]= y[sa[i]]==y[sa[i-1]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
46         if(p>=n)break;
47         m=p;
48     }
49 }
50 void getheight(){
51     int i,j,k=0;
52     for(i=0;i<n;i++)rank[sa[i]]=i;
53     for(i=0;i<n;i++){
54         if(k)k--;
55         if(rank[i]-1<0)continue;
56         j=sa[rank[i]-1];
57         while(s[j+k]==s[i+k])k++;
58         height[rank[i]]=k;
59     }
60 }
61 int ch[maxn][2],top=0;
62 bool find(int mid){
63     int ans=0,sum=1;
64     for(int i=1;i<n;i++){
65         chkmax(ans,sum);
66         if(height[i]<mid)sum=1;
67         else sum++;
68     }
69     return ans>=k;
70 }
71 int main(){
72     n=read(),k=read();
73     up(i,0,n-1)s[i]=read();s[n]=1000001;n++;
74     getsa(1000002);
75     getheight();
76     int left=0,right=1010000,mid,ans;
77     while(left<=right){
78         mid=(left+right)>>1;
79         if(find(mid))ans=mid,left=mid+1;
80         else right=mid-1;
81     }
82     cout<<ans<<endl;
83     return 0;
84 }

View Code

很早很早很早以前，在语言还没有出现时，人们的交流很困难。他们渐渐觉得应该用几个连续组合的符号来表示一件物品，于是他们想通过打造一个单词生成器来帮助他们完成这个工作（雾）,身为酋长，请你帮他们完成这个工作。

我们规定单词生成器的原理是这样的，对于一段字符串，比如CCCCC，按照从左到右的顺序连续抽取若干个字符，来组成一个新的单词，比如说上面那个例子对应的所有可生成的单词有 C CC CCC CCCC CCCCC,共五个，我们想知道对于一串字符串，最多可以生成多少个互不相同的单词.

求一个字符串有多少个子串，由于height数组已排序，在height数组里顺序扫一遍即可；

 1 /*chad*/
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<ctime>
 9 #include<string>
10 using namespace std;
11 const int maxn(1010),inf(1000000000);
12 #define FILE "dealing"
13 #define LL long long
14 #define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)
15 namespace IO{
16     char buf[1<<15],*fs,*ft;
17     LL gc(){return (fs==ft&&((ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft))?-1:*fs++;}
18     LL read(){
19         LL x=0,ch=gc(),f=0;
20         while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();}
21         while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
22         return f?-x:x;
23     }
24 }using namespace IO;
25 int n;
26 char s[maxn];
27 int rank[maxn],height[maxn],sa[maxn],t1[maxn],t2[maxn],c[maxn];
28 void getsa(int m){
29     int *x=t1,*y=t2;
30     for(int i=0;i<m;i++)c[i]=0;
31     for(int i=0;i<n;i++)c[x[i]=s[i]]++;
32     for(int i=1;i<m;i++)c[i]+=c[i-1];
33     for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
34     for(int k=1,p;k<=n;k<<=1){
35         p=0;
36         for(int i=n-k;i<n;i++)y[p++]=i;
37         for(int i=0;i<n;i++)if(sa[i]-k>=0)y[p++]=sa[i]-k;
38         for(int i=0;i<m;i++)c[i]=0;
39         for(int i=0;i<n;i++)c[x[y[i]]]++;
40         for(int i=1;i<m;i++)c[i]+=c[i-1];
41         for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
42         swap(x,y);
43         x[sa[0]]=0,p=1;
44         for(int i=1;i<n;i++)
45             x[sa[i]]= y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
46         m=p;
47         if(p>=n)break;
48     }
49 }
50 void getheight(){
51     int i,j,k=0;
52     for(i=0;i<n;i++)rank[sa[i]]=i;
53     for(i=0;i<n;i++){
54         if(k)k--;
55         if(rank[i]-1<0)continue;
56         j=sa[rank[i]-1];
57         while(s[j+k]==s[i+k])k++;
58         height[rank[i]]=k;
59     }
60 }
61 void slove(){
62     n=strlen(s);n++;
63     getsa(300);getheight();
64     int ans=0;
65     for(int i=1;i<n;i++)
66         ans+=n-1-sa[i]-height[i];
67     printf("%d
",ans);
68 }
69 int main(){
70     int T;
71     scanf("%d",&T);
72     while(T--){
73         scanf("%s",s);
74         slove();
75     }
76     return 0;
77 }

View Code

6.[后缀数组]最长回文串

maxcher或者后缀数组；

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 using namespace std;
 6 const int maxn=101000;
 7 int n=0,p[maxn<<2];
 8 char s[maxn<<2],s1[maxn],s2[maxn];
 9 int main()
10 {
11     //freopen("1.in","r",stdin);
12     scanf("%s",s1);
13     s[n++]='$';
14     for(int i=0;i<strlen(s1);i++)
15     {
16         s[n++]='#';
17         s[n++]=s1[i];
18     }
19     s[n++]='#';
20     int maxx=0,o=0;
21     for(int mx=0,id=0,i=1;i<n;i++)
22     {
23         if(mx>i)mx=min(p[(id<<1)-i],mx-i);
24         else p[i]=1;
25         while(s[i-p[i]]==s[i+p[i]])p[i]++;
26         if(p[i]+i>mx)
27         {
28             mx=p[i]+i;
29             id=i;
30         }
31         if(p[i]>maxx)maxx=p[i],o=i;
32     }
33     int len=0;
34     for(int i=o;i<maxx+o;i++)if(s[i]!='#')s2[++len]=s[i];
35     for(int i=len;i>=1;i--)cout<<s2[i];
36     for(int i=s[o]=='#'?1:2;i<=len;i++)cout<<s2[i];
37     return 0;
38 }

View Code

7.最长公共子串

将两个字符串连起来然后求即可；

 1 /*chad*/
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<ctime>
 9 #include<string>
10 using namespace std;
11 const int maxn(200010),inf(1000000000);
12 #define FILE "dealing"
13 #define LL long long
14 #define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)
15 namespace IO{
16     char buf[1<<15],*fs,*ft;
17     int gc(){return (fs==ft&&((ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft))?-1:*fs++;}
18     LL read(){
19         LL x=0,ch=gc(),f=0;
20         while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();}
21         while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
22         return f?-x:x;
23     }
24 }using namespace IO;
25 char s[maxn];
26 int n,p;
27 int sa[maxn],rank[maxn],t1[maxn],t2[maxn],c[maxn],height[maxn];
28 void getsa(int m){
29     int *x=t1,*y=t2;
30     for(int i=0;i<m;i++)c[i]=0;
31     for(int i=0;i<n;i++)c[x[i]=s[i]]++;
32     for(int i=1;i<m;i++)c[i]+=c[i-1];
33     for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
34     for(int k=1,p=0;k<=n;k<<=1){
35         p=0;
36         for(int i=n-k;i<n;i++)y[p++]=i;
37         for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
38         for(int i=0;i<m;i++)c[i]=0;
39         for(int i=0;i<n;i++)c[x[y[i]]]++;
40         for(int i=1;i<m;i++)c[i]+=c[i-1];
41         for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
42         swap(x,y);x[sa[0]]=0;p=1;
43         for(int i=1;i<n;i++)
44             x[sa[i]]= y[sa[i]]==y[sa[i-1]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
45         if(p>=n)break;
46         m=p;
47     }
48 }
49 void getheight(){
50     int j,k=0;
51     for(int i=0;i<n;i++)rank[sa[i]]=i;
52     for(int i=0;i<n;i++){
53         if(k)k--;
54         if(rank[i]-1<0)continue;
55         j=sa[rank[i]-1];
56         while(s[j+k]==s[i+k])k++;
57         height[rank[i]]=k;
58     }
59 }
60 bool check(int mid){
61     int flag[2]={0,0};
62     for(int i=1;i<n;i++){
63         if(flag[0]&&flag[1])return 1;
64         if(height[i]>=mid){
65             if(sa[i-1]<p)flag[0]=1;
66             else flag[1]=1;
67             if(sa[i]<p)flag[0]=1;
68             else flag[1]=1;
69         }
70         else flag[0]=flag[1]=0;
71     }
72     return 0;
73 }
74 int main(){
75     scanf("%s",s);
76     n=strlen(s);n++;
77     scanf("%s",s+n);
78     p=strlen(s+n);swap(p,n);n+=p+1;s[n-1]=1;
79     getsa(300),getheight();
80     int ans=0;
81     for(int i=1;i<n;i++)if((sa[i]>p)==(sa[i-1]<p))ans=max(ans,height[i]);
82     printf("%d
",ans);
83     return 0;
84 }

View Code