1 //rank从0开始 2 //sa从1开始,因为最后一个字符(最小的)排在第0位 3 //high从2开始,因为表示的是sa[i-1]和sa[i] 4 #define M 220000 5 int rank[M],sa[M],X[M],Y[M],high[M],init[M]; 6 int buc[M]; 7 void calhigh(int n) { 8 int i , j , k = 0; 9 for(i = 1 ; i <= n ; i++) rank[sa[i]] = i; 10 for(i = 0 ; i < n ; high[rank[i++]] = k) 11 for(k?k--:0 , j = sa[rank[i]-1] ; init[i+k] == init[j+k] ; k++); 12 } 13 bool cmp(int *r,int a,int b,int l) { 14 return (r[a] == r[b] && r[a+l] == r[b+l]); 15 } 16 void suffix(int n,int m = 128) { 17 int i , l , p , *x = X , *y = Y; 18 for(i = 0 ; i < m ; i ++) buc[i] = 0; 19 for(i = 0 ; i < n ; i ++) buc[ x[i] = init[i] ] ++; 20 for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; 21 for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[i] ]] = i; 22 for(l = 1,p = 1 ; p < n ; m = p , l *= 2) { 23 p = 0; 24 for(i = n-l ; i < n ; i ++) y[p++] = i; 25 for(i = 0 ; i < n ; i ++) if(sa[i] >= l) y[p++] = sa[i] - l; 26 for(i = 0 ; i < m ; i ++) buc[i] = 0; 27 for(i = 0 ; i < n ; i ++) buc[ x[y[i]] ] ++; 28 for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; 29 for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[y[i]] ] ] = y[i]; 30 for(swap(x,y) , x[sa[0]] = 0 , i = 1 , p = 1 ; i < n ; i ++) 31 x[ sa[i] ] = cmp(y,sa[i-1],sa[i],l) ? p-1 : p++; 32 } 33 calhigh(n-1);//后缀数组关键是求出high,所以求sa的时候顺便把rank和high求出来 34 } 35 36 37 //当需要反复询问两个后缀的最长公共前缀时用到RMQ 38 int Log[M]; 39 int best[20][M]; 40 void initRMQ(int n) {//初始化RMQ 41 for(int i = 1; i <= n ; i ++) best[0][i] = high[i]; 42 for(int i = 1; i <= Log[n] ; i ++) { 43 int limit = n - (1<<i) + 1; 44 for(int j = 1; j <= limit ; j ++) { 45 best[i][j] = min(best[i-1][j] , best[i-1][j+(1<<i>>1)]); 46 } 47 } 48 } 49 int lcp(int a,int b) {//询问a,b后缀的最长公共前缀 50 a = rank[a]; b = rank[b]; 51 if(a > b) swap(a,b); 52 a ++; 53 int t = Log[b - a + 1]; 54 return min(best[t][a] , best[t][b - (1<<t) + 1]); 55 } 56 57 58 int main() { 59 //预处理每个数字的Log值,常数优化,用于RMQ 60 Log[0] = -1; 61 for(int i = 1; i <= M ; i ++) { 62 Log[i] = (i&(i-1)) ? Log[i-1] : Log[i-1] + 1 ; 63 } 64 //******************************************* 65 // n为数组长度,下标0开始 66 // 将初始数据,保存在init里,并且保证每个数字都比0大 67 // m = max{ init[i] } + 1 68 // 一般情况下大多是字符操作,所以128足够了 69 //******************************************* 70 init[n] = 0; 71 suffix(n+1,m); 72 73 initRMQ(n); 74 }
hdu2890
http://acm.hdu.edu.cn/showproblem.php?pid=2890
整个题意是求最长公共不重叠子串且数量要大于k。
在开始的时候要对串离散化。
直接二分答案判断是否可行。直接将heigh数组扫一遍，然后贪心是否满足，在外面开个标记，记录满足的后缀。（开始用map，vector，码码能力还是这么搓。）
1 //rank从0开始 2 //sa从1开始,因为最后一个字符(最小的)排在第0位 3 //high从2开始,因为表示的是sa[i-1]和sa[i] 4 #define M 220000 5 #include <cstdio> 6 #include <cstring> 7 #include <iostream> 8 #include <map> 9 #include <vector> 10 #include <algorithm> 11 12 using namespace std; 13 14 15 int rank[M],sa[M],X[M],Y[M],high[M],init[M]; 16 int buc[M]; 17 void calhigh(int n) { 18 int i , j , k = 0; 19 for(i = 1 ; i <= n ; i++) rank[sa[i]] = i; 20 for(i = 0 ; i < n ; high[rank[i++]] = k) 21 for(k?k--:0 , j = sa[rank[i]-1] ; init[i+k] == init[j+k] ; k++); 22 } 23 bool cmp(int *r,int a,int b,int l) { 24 return (r[a] == r[b] && r[a+l] == r[b+l]); 25 } 26 void suffix(int n,int m = 128) { 27 int i , l , p , *x = X , *y = Y; 28 for(i = 0 ; i < m ; i ++) buc[i] = 0; 29 for(i = 0 ; i < n ; i ++) buc[ x[i] = init[i] ] ++; 30 for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; 31 for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[i] ]] = i; 32 for(l = 1,p = 1 ; p < n ; m = p , l *= 2) { 33 p = 0; 34 for(i = n-l ; i < n ; i ++) y[p++] = i; 35 for(i = 0 ; i < n ; i ++) if(sa[i] >= l) y[p++] = sa[i] - l; 36 for(i = 0 ; i < m ; i ++) buc[i] = 0; 37 for(i = 0 ; i < n ; i ++) buc[ x[y[i]] ] ++; 38 for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; 39 for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[y[i]] ] ] = y[i]; 40 for(swap(x,y) , x[sa[0]] = 0 , i = 1 , p = 1 ; i < n ; i ++) 41 x[ sa[i] ] = cmp(y,sa[i-1],sa[i],l) ? p-1 : p++; 42 } 43 calhigh(n-1);//后缀数组关键是求出high,所以求sa的时候顺便把rank和high求出来 44 } 45 46 47 //当需要反复询问两个后缀的最长公共前缀时用到RMQ 48 int Log[M]; 49 int best[20][M]; 50 void initRMQ(int n) {//初始化RMQ 51 for(int i = 1; i <= n ; i ++) best[0][i] = high[i]; 52 for(int i = 1; i <= Log[n] ; i ++) { 53 int limit = n - (1<<i) + 1; 54 for(int j = 1; j <= limit ; j ++) { 55 best[i][j] = min(best[i-1][j] , best[i-1][j+(1<<i>>1)]); 56 } 57 } 58 } 59 int lcp(int a,int b) {//询问a,b后缀的最长公共前缀 60 a = rank[a]; b = rank[b]; 61 if(a > b) swap(a,b); 62 a ++; 63 int t = Log[b - a + 1]; 64 return min(best[t][a] , best[t][b - (1<<t) + 1]); 65 } 66 67 struct node{ 68 int id; 69 int r; 70 friend bool operator < (const node &a,const node &b){ 71 if(a.r<b.r)return 1; 72 return 0; 73 } 74 }; 75 int g[100000]; 76 int r2k[100000]; 77 node mp[100000]; 78 int ans; 79 int n,k; 80 bool check(int mid,int sz){ 81 82 int i; 83 int flag=0,res=1; 84 sort(g,g+sz); 85 for(i=1;i<sz;i++){ 86 if(g[i]-g[flag]>=mid){ 87 res++;flag=i; 88 } 89 } 90 if(res>=k)return 1; 91 return 0; 92 } 93 bool solve(int mid){ 94 int i; 95 int res; 96 int flag; 97 g[0]=sa[1]; 98 int sz=1; 99 for(i=2;i<=n;i++){ 100 if(high[i]>=mid){ 101 g[sz++]=sa[i]; 102 } 103 else{ 104 if(check(mid,sz)){ 105 ans=sa[i-1]; 106 return 1; 107 } 108 else{ 109 sz=0; 110 g[sz++]=sa[i]; 111 } 112 } 113 } 114 if(check(mid,sz)){ 115 ans=sa[i-1]; 116 return 1; 117 } 118 return 0; 119 } 120 int main() { 121 //预处理每个数字的Log值,常数优化,用于RMQ 122 Log[0] = -1; 123 for(int i = 1; i <= M ; i ++) { 124 Log[i] = (i&(i-1)) ? Log[i-1] : Log[i-1] + 1 ; 125 } 126 //******************************************* 127 // n为数组长度,下标0开始 128 // 将初始数据,保存在init里,并且保证每个数字都比0大 129 // m = max{ init[i] } + 1 130 // 一般情况下大多是字符操作,所以128足够了 131 //******************************************* 132 int T; 133 int i,j; 134 int id; 135 int flag; 136 int l,r,mid; 137 138 cin>>T; 139 140 while(T--){ 141 142 143 cin>>n>>k; 144 for(i=0;i<n;i++){ 145 scanf("%d",&mp[i].r); 146 mp[i].id=i; 147 } 148 sort(mp,mp+n); 149 id=1;init[mp[0].id]=1; 150 r2k[1]=mp[0].r; 151 for(int i=1;i<n;i++){ 152 if(mp[i].r!=mp[i-1].r){ 153 id++; 154 init[mp[i].id]=id; 155 r2k[id]=mp[i].r; 156 } 157 else{ 158 init[mp[i].id]=id; 159 } 160 } 161 init[i]=0; 162 suffix(n+1,id+5); 163 l=0,r=n+1; 164 while(l<=r){ 165 mid=(l+r)/2; 166 if(solve(mid)) 167 l=mid+1; 168 else 169 r=mid-1; 170 } 171 cout<<l-1<<endl; 172 for(i=0;i<l-1;i++) 173 printf("%d\n",r2k[init[ans+i]]); 174 if(T!=0) 175 printf("\n"); 176 } 177 /*init[n] = 0; 178 suffix(n+1,m); 179 180 initRMQ(n);*/ 181 }
poj2774
题意是求两个串的最长公共子串。
将两个串连接中间用个非字符集的字符（模板都是转化到init数组，中间用0连接）。在扫一遍heigh数组，条件是i和i-1所对应的后缀分别在两个串内。（
延伸一下，多个字符串求最长公共子串，将所有字符串连接，思路相同。不过应该会麻烦点。。。
）
//rank从0开始 //sa从1开始,因为最后一个字符(最小的)排在第0位 //high从2开始,因为表示的是sa[i-1]和sa[i] #include<iostream> #include<cstdio> #include<cstring> #define M 220000 using namespace std; int rank[M],sa[M],X[M],Y[M],high[M],init[M]; int buc[M]; void calhigh(int n) { int i , j , k = 0; for(i = 1 ; i <= n ; i++) rank[sa[i]] = i; for(i = 0 ; i < n ; high[rank[i++]] = k) for(k?k--:0 , j = sa[rank[i]-1] ; init[i+k] == init[j+k] ; k++); } bool cmp(int *r,int a,int b,int l) { return (r[a] == r[b] && r[a+l] == r[b+l]); } void suffix(int n,int m = 128) { int i , l , p , *x = X , *y = Y; for(i = 0 ; i < m ; i ++) buc[i] = 0; for(i = 0 ; i < n ; i ++) buc[ x[i] = init[i] ] ++; for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[i] ]] = i; for(l = 1,p = 1 ; p < n ; m = p , l *= 2) { p = 0; for(i = n-l ; i < n ; i ++) y[p++] = i; for(i = 0 ; i < n ; i ++) if(sa[i] >= l) y[p++] = sa[i] - l; for(i = 0 ; i < m ; i ++) buc[i] = 0; for(i = 0 ; i < n ; i ++) buc[ x[y[i]] ] ++; for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[y[i]] ] ] = y[i]; for(swap(x,y) , x[sa[0]] = 0 , i = 1 , p = 1 ; i < n ; i ++) x[ sa[i] ] = cmp(y,sa[i-1],sa[i],l) ? p-1 : p++; } calhigh(n-1);//后缀数组关键是求出high,所以求sa的时候顺便把rank和high求出来 } //当需要反复询问两个后缀的最长公共前缀时用到RMQ int Log[M]; int best[20][M]; void initRMQ(int n) {//初始化RMQ for(int i = 1; i <= n ; i ++) best[0][i] = high[i]; for(int i = 1; i <= Log[n] ; i ++) { int limit = n - (1<<i) + 1; for(int j = 1; j <= limit ; j ++) { best[i][j] = min(best[i-1][j] , best[i-1][j+(1<<i>>1)]); } } } int lcp(int a,int b) {//询问a,b后缀的最长公共前缀 a = rank[a]; b = rank[b]; if(a > b) swap(a,b); a ++; int t = Log[b - a + 1]; return min(best[t][a] , best[t][b - (1<<t) + 1]); } char str1[100001],str2[100001]; int main() { //预处理每个数字的Log值,常数优化,用于RMQ Log[0] = -1; for(int i = 1; i <= M ; i ++) { Log[i] = (i&(i-1)) ? Log[i-1] : Log[i-1] + 1 ; } //******************************************* // n为数组长度,下标0开始 // 将初始数据,保存在init里,并且保证每个数字都比0大 // m = max{ init[i] } + 1 // 一般情况下大多是字符操作,所以128足够了 //******************************************* int i,j; int n; int l1,r1,l2,r2; while(~scanf("%s%s",str1,str2)){ for(i=0;str1[i]!=‘\0‘;i++)init[i]=str1[i]-‘a‘+1; l1=0,r1=i-1; init[i++]=0; l2=i; for(j=0;str2[j]!=‘\0‘;j++)init[i++]=str2[j]-‘a‘+1; r2=i-1; init[i]=0; n=i; suffix(n+1,128); int ans=0; for(i=3;i<=n;i++){ if(high[i]>ans&&(sa[i]>=l1&&sa[i]<=r1&&sa[i-1]>=l2&&sa[i-1]<=r2|| sa[i]>=l2&&sa[i]<=r2&&sa[i-1]>=l1&&sa[i-1]<=r1)){ ans=high[i]; } } printf("%d\n",ans); } /*init[n] = 0; suffix(n+1,m); initRMQ(n); */ }
原文：http://www.cnblogs.com/youyouyou/p/3633306.html
