后缀数组

不可重叠最长重复子串 http://poj.org/problem?id=1743

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 class Suffix_Array {  ///后缀数组
 5     static const int MV=20010;///串长度
 6     int n,m,i,j,k,p,str[MV],sa[MV],height[MV],Rank[MV],wa[MV],wb[MV],wv[MV],ws[MV];///sa按字典序排序后后缀下标,rank后缀的排名,height排名相邻两个后缀的最长公共前缀
 7     bool cmp(int r[],int a,int b,int len) {
 8         return r[a]==r[b]&&r[a+len]==r[b+len];
 9     }
10     void buildsa() {
11         int *x=wa,*y=wb;
12         for(i=0; i<m; i++) ws[i]=0;
13         for(i=0; i<n; i++) ws[x[i]=str[i]]++;
14         for(i=1; i<m; i++) ws[i]+=ws[i-1];
15         for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;
16         for(j=p=1; p<n; j<<=1,m=p) {
17             for(p=0,i=n-j; i<n; i++) y[p++]=i;
18             for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
19             for(i=0; i<m; i++) ws[i]=0;
20             for(i=0; i<n; i++) ws[wv[i]=x[y[i]]]++;
21             for(i=1; i<m; i++) ws[i]+=ws[i-1];
22             for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];
23             for(swap(x,y),x[sa[0]]=0,p=i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
24         }
25     }
26     void buildheight() {
27         for(i=1; i<=n-1; i++) Rank[sa[i]]=i;
28         for(i=k=0; i<n-1; height[Rank[i++]]=k)
29             for(k?k--:0,j=sa[Rank[i]-1]; str[i+k]==str[j+k]; k++);
30     }
31 public:
32     int getsa(int id) {
33         return sa[id];
34     }
35     int getheight(int id) {
36         return height[id];
37     }
38     int getrank(int id) {
39         return Rank[id];
40     }
41     void build(int s[],int len,int cl) {///n为字符串长度加一,m为最大字符值加一
42         n=len;
43         m=cl;
44         for(int i=0; i<=len; i++) str[i]=s[i];
45         str[len]=0;
46         buildsa();
47         buildheight();
48     }
49 } gx;
50 int n;
51 bool judge(int len) {
52     int up,down;
53     up=down=gx.getsa(1);
54     for(int i=2; i<=n; i++) {
55         if(gx.getheight(i)<len) {
56             up=down=gx.getsa(i);
57         } else {
58             up=max(up,gx.getsa(i));
59             down=min(down,gx.getsa(i));
60             if(up-down>len) return true;
61         }
62     }
63     return false;
64 }
65 int Bins(int L,int R) {
66     while(L<=R) {
67         int mid=(L+R)>>1;
68         if(judge(mid)) {
69             L=mid+1;
70         } else {
71             R=mid-1;
72         }
73     }
74     return R+1;
75 }
76 int a[20010];
77 int main() {
78     while(~scanf("%d",&n),n) {
79         for(int i=0; i<n; i++) {
80             scanf("%d",&a[i]);
81         }
82         for(int i=0; i<n-1; i++) {
83             a[i]=a[i+1]-a[i]+88;
84         }
85         a[n-1]=0;
86         gx.build(a,n,177);
87         int ans=Bins(4,n);
88         if(ans<5) ans=0;
89         printf("%d\n",ans);
90     }
91     return 0;
92 }
View Code

 

 

 可重叠的k 次最长重复子串 http://poj.org/problem?id=3261

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int M=2000100;  //可重叠的k 次最长重复子串
 5 class Suffix_Array {  ///后缀数组
 6     static const int MV=M;///串长度
 7     int n,m,i,j,k,p,str[MV],sa[MV],height[MV],Rank[MV],wa[MV],wb[MV],wv[MV],ws[MV];///sa按字典序排序后后缀下标,rank后缀的排名,height排名相邻两个后缀的最长公共前缀
 8     bool cmp(int r[],int a,int b,int len) {
 9         return r[a]==r[b]&&r[a+len]==r[b+len];
10     }
11     void buildsa() {
12         int *x=wa,*y=wb;
13         for(i=0; i<m; i++) ws[i]=0;
14         for(i=0; i<n; i++) ws[x[i]=str[i]]++;
15         for(i=1; i<m; i++) ws[i]+=ws[i-1];
16         for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;
17         for(j=p=1; p<n; j<<=1,m=p) {
18             for(p=0,i=n-j; i<n; i++) y[p++]=i;
19             for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
20             for(i=0; i<m; i++) ws[i]=0;
21             for(i=0; i<n; i++) ws[wv[i]=x[y[i]]]++;
22             for(i=1; i<m; i++) ws[i]+=ws[i-1];
23             for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];
24             for(swap(x,y),x[sa[0]]=0,p=i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
25         }
26     }
27     void buildheight() {
28         for(i=1; i<=n-1; i++) Rank[sa[i]]=i;
29         for(i=k=0; i<n-1; height[Rank[i++]]=k)
30             for(k?k--:0,j=sa[Rank[i]-1]; str[i+k]==str[j+k]; k++);
31     }
32 public:
33     int getsa(int id) {
34         return sa[id];
35     }
36     int getheight(int id) {
37         return height[id];
38     }
39     int getrank(int id) {
40         return Rank[id];
41     }
42     void build(int s[],int len,int cl) {///n为字符串长度加一,m为最大字符值加一
43         n=len;
44         m=cl;
45         for(int i=0; i<=len; i++) str[i]=s[i];
46         str[len]=0;
47         buildsa();
48         buildheight();
49     }
50 } gx;
51 int n,k;
52 bool judge(int len) {
53     int cnt;
54     for(int i=2; i<=n; i++) {
55         if(gx.getheight(i)<len) {
56             cnt=1;
57         } else {
58             cnt++;
59             if(cnt>=k) return true;
60         }
61     }
62     return false;
63 }
64 int Bins(int L,int R) {
65     while(L<=R) {
66         int mid=(L+R)>>1;
67         if(judge(mid)) {
68             L=mid+1;
69         } else {
70             R=mid-1;
71         }
72     }
73     return L-1;
74 }
75 int a[M];
76 int main() {
77     while(~scanf("%d%d",&n,&k)) {
78         for(int i=0; i<n; i++) {
79             scanf("%d",&a[i]);
80             a[i]++;
81         }
82         gx.build(a,n+1,1000010);
83         int ans=Bins(1,n);
84         printf("%d\n",ans);
85     }
86     return 0;
87 }
View Code

 

 

不相同的子串的个数 http://www.spoj.com/problems/SUBST1/

 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 class Suffix_Array {  ///后缀数组
 7     static const int MV=50010;///串长度
 8     int n,m,i,j,k,p,str[MV],sa[MV],height[MV],Rank[MV],wa[MV],wb[MV],wv[MV],ws[MV];///sa按字典序排序后后缀下标,rank后缀的排名,height排名相邻两个后缀的最长公共前缀
 9     bool cmp(int r[],int a,int b,int len) {
10         return r[a]==r[b]&&r[a+len]==r[b+len];
11     }
12     void buildsa() {
13         int *x=wa,*y=wb;
14         for(i=0; i<m; i++) ws[i]=0;
15         for(i=0; i<n; i++) ws[x[i]=str[i]]++;
16         for(i=1; i<m; i++) ws[i]+=ws[i-1];
17         for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;
18         for(j=p=1; p<n; j<<=1,m=p) {
19             for(p=0,i=n-j; i<n; i++) y[p++]=i;
20             for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
21             for(i=0; i<m; i++) ws[i]=0;
22             for(i=0; i<n; i++) ws[wv[i]=x[y[i]]]++;
23             for(i=1; i<m; i++) ws[i]+=ws[i-1];
24             for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];
25             for(swap(x,y),x[sa[0]]=0,p=i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
26         }
27     }
28     void buildheight() {
29         for(i=1; i<=n-1; i++) Rank[sa[i]]=i;
30         for(i=k=0; i<n-1; height[Rank[i++]]=k)
31             for(k?k--:0,j=sa[Rank[i]-1]; str[i+k]==str[j+k]; k++);
32     }
33 public:
34     int getsa(int id) {
35         return sa[id];
36     }
37     int getheight(int id) {
38         return height[id];
39     }
40     int getrank(int id) {
41         return Rank[id];
42     }
43     void build(char s[],int len,int cl) {///n为字符串长度加一,m为最大字符值加一
44         n=len;
45         m=cl;
46         for(int i=0; i<=len; i++) str[i]=s[i];
47         str[len]=0;
48         buildsa();
49         buildheight();
50     }
51 } gx;
52 char a[50010];
53 int main() {
54     int t;
55     while(~scanf("%d",&t)) {
56         while(t--){
57             scanf("%s",a);
58             int n=strlen(a);
59             gx.build(a,n+1,256);
60             LL ans=0;
61             for(int i=1;i<=n;i++){
62                 ans+=n-gx.getsa(i)-gx.getheight(i);
63             }
64             printf("%lld\n",ans);
65         }
66     }
67     return 0;
68 }
View Code

 

 

 

 

end

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。