后缀数组基本模板
①倍增法（时间O(NlogN）,空间O(N)）
1 #include<iostream> 2 using namespace std; 3 const int maxl = 100010; 4 char s[maxl]; 5 int totlen; 6 int r2[maxl], cc[maxl],SA[maxl], RANK[maxl], Height[maxl]; 7 //r2:以第二关键字对后缀排序所得的辅助数组 8 //cc:计数排序辅助数组 9 //RANK：RANK数组,RANK[i]表示后缀i~totlen-1（Suffix[i]）在所有后缀中的排名 10 //Height[i]:表示Suffix[SA[i]]和Suffix[SA[i - 1]]的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀 11 //SA[i]:后缀数组，满足Suffix[SA[1]] < Suffix[SA[2]] …… < Suffix[SA[Len]],即排名为i的后缀为Suffix[SA[i]] (与Rank是互逆运算) 12 bool Cmp(int *Rank, int idx1, int idx2, int len) 13 {//比较两个串是否相同，比较两个关键字 14 int a1 = Rank[idx1]; 15 int b1 = Rank[idx2]; 16 int a2 = (idx1 + len >= totlen ? -1 : Rank[idx1 + len]); 17 int b2 = (idx2 + len >= totlen ? -1 : Rank[idx2 + len]); 18 return a1 == b1&&a2 == b2; 19 } 20 void Build_SA() 21 { 22 int m = 26;// 单字符rank的范围 23 //计数排序 24 for (int i = 0; i < m; i++) cc[i] = 0; 25 for (int i = 0; i < totlen; i++) ++cc[RANK[i] = (s[i] - 'a')]; 26 for (int i = 1; i < m; i++) cc[i] += cc[i - 1]; 27 for (int i = totlen - 1; i >= 0; --i) SA[--cc[RANK[i]]] = i; 28 29 for (int k = 1; k <= totlen; k <<= 1) 30 { 31 int p = 0; 32 33 for (int i = totlen - k; i < totlen; i++) 34 {//第二关键字为空的后缀放在最开头 35 r2[p++] = i; 36 } 37 for (int i = 0; i < totlen; i++) 38 {//接着放第二关键字不为空的 39 if (SA[i] >= k) r2[p++] = SA[i] - k; 40 } 41 //计数排序 42 for (int i = 0; i < m; i++) cc[i] = 0; 43 for (int i = 0; i < totlen; i++) ++cc[RANK[i]]; 44 //for (int i = 0; i < totlen; i++) ++cc[RANK[r2[i]]]; 45 for (int i = 1; i < m; i++) cc[i] += cc[i - 1]; 46 for (int i = totlen - 1; i >= 0; --i) SA[--cc[RANK[r2[i]]]] = r2[i]; 47 48 swap(RANK, r2); 49 m = 1; 50 RANK[SA[0]] = 0; 51 //r2指向旧的rank数组 52 for (int i = 1; i < totlen; i++) RANK[SA[i]] = (Cmp(r2, SA[i], SA[i - 1], k) ? m - 1 : m++); 53 54 if (m >= totlen) break; 55 } 56 } 57 void Build_Height() 58 { 59 for (int i = 0; i < totlen; i++) RANK[SA[i]] = i; 60 Height[0] = 0; 61 int k = 0; 62 for (int i = 0; i < totlen; i++) 63 { 64 if (!RANK[i]) continue; 65 int j = SA[RANK[i] - 1]; 66 if (k) k--; 67 while (s[i + k] == s[j + k]) k++; 68 Height[RANK[i]] = k; 69 } 70 } 71 72 int main() 73 { 74 scanf("%s", s); 75 totlen = strlen(s); 76 Build_SA(); 77 Build_Height(); 78 for (int i = 0; i < totlen; i++) printf("%d ", SA[i]); 79 printf("\n"); 80 for (int i = 0; i < totlen; i++) printf("%d ", Height[i]); 81 printf("\n"); 82 83 84 return 0; 85 } 86 //abcabcabcabc 87 //9 6 3 0 10 7 4 1 11 8 5 2 88 //0 3 6 9 0 2 5 8 0 1 4 7
②DC3（时间O(N）,空间O(N)）
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 #define F(x) ((x)/3+((x)%3==1?0:tb)) 7 #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) 8 const int maxn = 1e5 + 10; 9 int WA[maxn], WB[maxn], WV[maxn], WS[maxn]; 10 int r[maxn*3], SA[maxn*3]; 11 //SA[i]:后缀数组，满足Suffix[SA[1]] < Suffix[SA[2]] …… < Suffix[SA[Len]], 12 //即排名为i的后缀为Suffix[SA[i]] (与Rank是互逆运算) 13 //1~n 14 int c0(int *r, int a, int b) 15 { 16 return r[a] == r[b] && r[a + 1] == r[b + 1] && r[a + 2] == r[b + 2]; 17 } 18 int c12(int k, int *r, int a, int b) 19 { 20 if (k == 2) return r[a] < r[b] || r[a] == r[b] && c12(1, r, a + 1, b + 1); 21 else return r[a] < r[b] || r[a] == r[b] && WV[a + 1] < WV[b + 1]; 22 } 23 void sort(int *r, int *a, int *b, int n, int m) 24 {//r保存数据，a保存待排序字符下标，b保存3长度字符串的首字符下标，m表示基数的容量,ascii最多128 25 int i; 26 for (i = 0; i < n; i++) WV[i] = r[a[i]];//WV表示待排序字符 27 for (i = 0; i < m; i++) WS[i] = 0;//初始化桶 28 for (i = 0; i < n; i++) WS[WV[i]]++;//对应桶自增 29 for (i = 1; i < m; i++) WS[i] += WS[i - 1];//使每一个桶都能反映出排名 30 for (i = n - 1; i >= 0; i--) b[--WS[WV[i]]] = a[i];//按照排名重新存储a 31 return; 32 } 33 void dc3(int *r, int *sa, int n, int m) 34 {//n=strlen+1，最后一位补0 35 int i, j, *rn = r + n, *san = sa + n, ta = 0, tb = (n + 1) / 3, tbc = 0, p; 36 r[n] = r[n + 1] = 0; 37 for (i = 0; i < n; i++) if (i % 3 != 0) WA[tbc++] = i; 38 sort(r + 2, WA, WB, tbc, m); 39 sort(r + 1, WB, WA, tbc, m); 40 sort(r, WA, WB, tbc, m); 41 for (p = 1, rn[F(WB[0])] = 0, i = 1; i < tbc; i++) 42 rn[F(WB[i])] = c0(r, WB[i - 1], WB[i]) ? p - 1 : p++; 43 if (p < tbc) dc3(rn, san, tbc, p); 44 else for (i = 0; i < tbc; i++) san[rn[i]] = i; 45 for (i = 0; i < tbc; i++) if (san[i] < tb) WB[ta++] = san[i] * 3; 46 if (n % 3 == 1) WB[ta++] = n - 1; 47 sort(r, WB, WA, ta, m); 48 for (i = 0; i < tbc; i++) WV[WB[i] = G(san[i])] = i; 49 for (i = 0, j = 0, p = 0; i < ta && j < tbc; p++) 50 sa[p] = c12(WB[j] % 3, r, WA[i], WB[j]) ? WA[i++] : WB[j++]; 51 for (; i < ta; p++) sa[p] = WA[i++]; 52 for (; j < tbc; p++) sa[p] = WB[j++]; 53 return; 54 } 55 int Rank[maxn], Height[maxn]; 56 //RANK：RANK数组,RANK[i]表示后缀i~totlen-1（Suffix[i]）在所有后缀中的排名,0~n-1 57 //Height[i]:表示Suffix[SA[i]]和Suffix[SA[i - 1]]的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀,1~n 58 void calheight(int *r, int *sa, int n) 59 {//n为strlen 60 int i, j, k = 0; 61 for (i = 1; i <= n; i++) Rank[sa[i]] = i;//sa[0]指到了末尾，排名从1开始 62 for (i = 0; i < n; Height[Rank[i++]] = k) 63 for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++); 64 return; 65 } 66 int mm[maxn]; 67 int dp[maxn][20]; 68 void initRMQ(int n) 69 { 70 int i, j, a, b; 71 for (mm[0] = -1, i = 1; i <= n; i++) 72 mm[i] = ((i&(i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1]; 73 for (i = 1; i <= n; i++) dp[i][0] = Height[i]; 74 for (i = 1; i <= mm[n]; i++) 75 for (j = 1; j+(1<<i)-1 <= n; j++) 76 { 77 a = dp[j][i-1]; 78 b = dp[j + (1 << (i - 1))][i-1]; 79 if (a < b) dp[j][i] = a; 80 else dp[j][i] = b; 81 } 82 return; 83 } 84 int askRMQ(int a, int b) 85 { 86 int t; 87 t = mm[b - a + 1]; 88 b -= (1 << t) - 1; 89 a = dp[a][t]; b = dp[b][t]; 90 return a < b ? a : b; 91 } 92 int lcp(int a, int b,int len)//求以a，b开始的子串的最长公共前缀,0~n-1,len=n 93 { 94 if (a == b) return len - a; 95 a = Rank[a]; b = Rank[b]; 96 if (a > b) swap(a, b); 97 return(askRMQ(a + 1, b)); 98 } 99 char s[maxn]; 100 struct pi { 101 int x; 102 int y; 103 }pp[maxn]; 104 int main() 105 { 106 scanf("%s", s); 107 int n = strlen(s); 108 for (int i = 0; i < n; i++) { 109 r[i] = s[i]; 110 } 111 r[n] = 0; 112 dc3(r, SA, n + 1, 128); 113 calheight(r, SA, n); 114 //输出排名为i的后缀的起始下标(0开始) 115 for (int i = 1; i <= n; i++) printf("%d ", SA[i]); 116 printf("\n"); 117 //输出排名为i的后缀与前一个后缀的最长公共前缀长度 118 for (int i = 1; i <= n; i++) printf("%d ", Height[i]); 119 printf("\n"); 120 //输出下标从i开始的后缀的排名 121 for (int i = 0; i < n; i++) printf("%d ", Rank[i]); 122 printf("\n"); 123 //输出两两后缀之间的最长公共前缀 124 initRMQ(n); 125 for (int i = 0; i <n; i++) 126 { 127 for (int j = i; j <n; j++) printf("%d ", lcp(i, j,n)); 128 printf("\n"); 129 } 130 }
一些应用
1、给定一个字符串，求两个后缀的最大公共前缀
求解LCP，转化为求某个区间的height的最小值，可用RMQ求解
2、给定一个字符串，求最长重复子串，子串可重叠
求解height数组最大值即可。求最长重复子串，等价于求两个后缀的最大公共前缀的最大值。因为任意两个后缀的最大公共前缀为height数组中某一区间的最小值，这个值一定不大于height数组最大值。
3、给定一个字符串，求最长重复子串，子串不可重叠
二分答案，判断是否存在两个长度为k的子串是相同的，且不重叠。对当前k，遍历height数组，将连续的若干后缀且之间的最大公共前缀>=k的分为一组，若有一组中sa的最大值和最小值之差不小于k，则存在。
4、给定一个字符串，求至少出现k次的最长重复子串，子串可重叠
同样二分答案，将height数组分为若干组，判断有没有一个组的后缀的个数不小于k。
5、给定一个字符串，求不相同子串的数目。
每个子串一定是某个后缀的前缀，原问题等价于求所有后缀之间的不相同的前缀的个数。对每个suffx(sa[i]),将贡献n-sa[i]+1-height[i]个不同子串，累加即为答案。
6、给定一个字符串，求最长回文子串。
穷举每一位，计算以这个字符为中心的最长会问子串。怎么计算呢？将整个字符串反过来写在原串的后面，中间用一个特殊字符隔开，这样就转化为求这个新字符串的某两个后缀（这两个后缀由穷举的该位确定）的最长公共前缀。
7、给定一个字符串L，已知这个字符串是由某个字符串S重复R此得到的，求R的最大值。
穷举字符串S的长度为k，先看L的长度能否被k整除，再看suffix(1)与suffix(k+1)的最大公共前缀是否等于n-k。
8、给定一个字符串，求重复次数最多的连续重复子串。
穷举长度L，求长度为L的子串最多能连续出现几次。如果该子串S在原串出现2次，则S肯定包括了字符r[0]、r[L]、r[L*2]、……中某相邻的两个。故只需看字符r[L*i]和r[L*(i+1)]开始往前和往后各能匹配多远，记往前和往后的距离和为K，则连续出现K/L+1次。
9、给定两个字符串A和B，求最长公共子串。
等价于求A的后缀和B的后缀的最长公共前缀的最大值。将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，求这个新字符串的后缀数组。求当suffix(sa[i-1])与suffix(sa[i])不是同一个字符串时height[i]的最大值。
10、给定两个字符串A和B，求长度不小于k的公共子串个数（可以相同，位置不同即可）
比如xx与xx的长度不小于1的公共子串的个数为5。思路为计算A的所有后缀和B的所有后缀之间的最大公共前缀的长度，将长度不小于k的相加。将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，求这个新字符串的后缀数组。按height分组，快速统计每组中后缀之间的最长公共前缀之和。每遇到一个B的后缀就统计与前面的A的后缀能产生多少个长度不小于k的公共子串，A的后缀需要用单调栈维护。
11、给定n个字符串，求出现在不小于k个字符串中的最长子串。
将n个字符串串接，中间用一个没有出现的字符隔开，求后缀数组。二分答案，将height分为若干组，判断每组的后缀是否出现在不小于k个原串中。
12、给定n个字符串，求在每个字符串中至少出现2次且不重叠的最长子串。
将n个字符串串接，中间用一个没有出现的字符隔开，求后缀数组。二分答案，将height分为若干组，判断是否有一组后缀在每个原来的字符串中至少出现两次，并且在每个原来的字符串中，后缀的起始位置的最大值和最小值之差是否不小于当前答案。（若不要求不重叠，则无需判断）
13、给定n个字符串，求出现或反转后出现每个字符串的最长子串
将n个字符串反过来串接，中间用一个没有出现的字符隔开，求后缀数组。二分答案，将height分为若干组，判断是否有一组后缀在每个原来的字符串或反转后的字符串中出现。
参考：https://wenku.baidu.com/view/5b886b1ea76e58fafab00374.html###
———————————————————————————————————————————————————
———————————————————————————————————————————————————
1、poj 1743 Musical Theme
题意：给你一个长度为n(1<=n<=20000)的数字串。如果一个串在母串出现的次数大于一次那么这个串就是母串的重复子串。子串的每个位置同时加上一个数字重复出现在另一个位置也算重复。先在问这个母串最长的不相交即没有重复元素的重复子串的最大长度。
思路：后缀数组。对于题目所给的加上一个数字重复的情况。可以令s[i]=s[i+1]-s[i]，直接转换成求字符串最长公共前缀。
求不相交重复子串：二分最大长度k。然后再用后缀数组判定。这样我们就可以将height分组，其中每组的后缀之间的height 值都不小于k。容易看出，有希望成为最长公共前缀不小于k 的两个后缀一定在同一组。然后对于每组后缀，只须判断每个后缀的sa 值的最大值和最小值之差是否不小于k。如果有一组满足，则说明存在，否则不存在。
1 //题意：给你一个长度为n(1<=n<=20000)的数字串。如果一个串在母串出现的次数大于一次那么这个串就是母串的重复子串。子串的每个位置同时加上一个数字重复出现在另一个位置也算重复。先在问这个母串最长的不相交即没有重复元素的重复子串的最大长度。 2 #include<iostream> 3 #define min(a,b) ((a)<(b)?(a):(b)) 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 using namespace std; 6 const int MAX = 20050; 7 8 int n, num[MAX]; 9 int sa[MAX], Rank[MAX], height[MAX]; 10 int tp[MAX], wb[MAX], wv[MAX], tax[MAX]; 11 //sa:所有后缀的字典序中排第i位的在原串的起始位置为sa[i] 12 //Rank：原串中第i个位置开始的后缀在字典序的排名 13 //heiht:字典序中第i个和i-1个的后缀的最长公共前缀 14 //tp:rank的辅助数组(计数排序中的第二关键字),与SA意义一样。 15 //wb: 16 //wv: 17 //tax:基数排序辅助数组 18 int cmp(int *r, int a, int b, int l) 19 {//通过二元组两个下标的比较，确定两个子串是否相同 20 return r[a] == r[b] && r[a + l] == r[b + l]; 21 } 22 23 void getsa(int *r, int n, int m) 24 {//m为ASCII码的范围 25 int i, j, p, *x = tp, *y = wb, *t; 26 //基数排序 27 for (i = 0; i < m; i++) tax[i] = 0; 28 for (i = 0; i < n; i++) tax[x[i] = r[i]] ++; 29 for (i = 1; i < m; i++) tax[i] += tax[i - 1]; 30 for (i = n - 1; i >= 0; i--) sa[--tax[x[i]]] = i;//倒着枚举保证相对顺序 31 32 for (j = 1, p = 1; p < n; j *= 2, m = p) 33 {//把子串长度翻倍,更新rank 34 //j:当前一个字串的长度 35 //m:当前离散后的排名种类数 36 for (p = 0, i = n - j; i < n; i++) y[p++] = i; 37 for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;//按第二关键字排序.y[i]表示第二关键字排名第i的后缀起始位置 38 39 for (i = 0; i < n; i++) wv[i] = x[y[i]];//暂存 40 41 for (i = 0; i < m; i++) tax[i] = 0; 42 for (i = 0; i < n; i++) tax[wv[i]] ++;//x[i]表示起始位置为i的后缀的第一关键字排序 43 for (i = 1; i < m; i++) tax[i] += tax[i - 1]; 44 for (i = n - 1; i >= 0; i--) sa[--tax[wv[i]]] = y[i];//接着按第一关键字排序 45 46 for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++) 47 {////x[i]存排名第i后缀的排名 48 x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++; 49 } 50 } 51 } 52 53 void calHeight(int *r, int n) 54 { 55 int i, j, k = 0; 56 for (i = 1; i <= n; i++) Rank[sa[i]] = i; 57 for (i = 0; i < n; height[Rank[i++]] = k) 58 { 59 for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++); 60 } 61 } 62 63 bool valid(int len) 64 { 65 int i = 2, ma, mi;//区间下界和上界 66 while (1) 67 { 68 while (i <= n && height[i] < len) i++; 69 if (i > n) break; 70 ma = sa[i - 1]; 71 mi = sa[i - 1]; 72 while (i <= n && height[i] >= len) 73 { 74 ma = max(ma, sa[i]); 75 mi = min(mi, sa[i]); 76 i++; 77 } 78 if (ma - mi >= len) return true; 79 } 80 return false; 81 } 82 83 int main() 84 { 85 int i, ans; 86 while (scanf("%d", &n) && n != 0) 87 { 88 for (i = 0; i < n; i++) 89 { 90 scanf("%d", &num[i]); 91 } 92 if (n < 10) 93 {//如果小于10，则不相交重复子串字串长度不超过5，不符合题意 94 printf("0\n"); 95 continue; 96 } 97 n--; 98 for (i = 0; i < n; i++) 99 { 100 num[i] = num[i + 1] - num[i] + 89; 101 } 102 num[n] = 0; 103 getsa(num, n + 1, 200); 104 calHeight(num, n); 105 106 int low = 4, high = (n - 1) / 2, mid; 107 while (low < high) 108 { 109 mid = (low + high + 1) / 2; 110 if (valid(mid)) 111 { 112 low = mid; 113 } 114 else 115 { 116 high = mid - 1; 117 } 118 } 119 ans = low < 4 ? 0 : low + 1;//加回1 120 printf("%d\n", ans); 121 } 122 return 0; 123 }
2、UVA 12206 Stammering Aliens
题意：给定一个序列，求出现次数至少为m、长度最长的子串的最大起始下标
思路：对原串做完后缀数组后二分最大长度，对于每个二分值k，对height数组分组，如果某组中后缀数量大于等于m则找到这个组中sa[i]的最大值来更新答案值
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 int k; 6 7 //后缀数组模板 8 const int maxl = 40010; 9 char s[maxl]; 10 int totlen; 11 int r2[maxl], cc[maxl], SA[maxl], RANK[maxl], Height[maxl]; 12 //r2:以第二关键字对后缀排序所得的辅助数组 13 //cc:计数排序辅助数组 14 //RANK：RANK数组,RANK[i]表示后缀i~totlen-1（Suffix[i]）在所有后缀中的排名 15 //Height[i]:表示Suffix[SA[i]]和Suffix[SA[i - 1]]的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀 16 //SA[i]:后缀数组，满足Suffix[SA[1]] < Suffix[SA[2]] …… < Suffix[SA[Len]],即排名为i的后缀为Suffix[SA[i]] (与Rank是互逆运算) 17 bool Cmp(int *Rank, int idx1, int idx2, int len) 18 {//比较两个串是否相同，比较两个关键字 19 int a1 = Rank[idx1]; 20 int b1 = Rank[idx2]; 21 int a2 = (idx1 + len >= totlen ? -1 : Rank[idx1 + len]); 22 int b2 = (idx2 + len >= totlen ? -1 : Rank[idx2 + len]); 23 return a1 == b1&&a2 == b2; 24 } 25 void Build_SA() 26 { 27 int m = 26;// 单字符rank的范围 28 //计数排序 29 for (int i = 0; i < m; i++) cc[i] = 0; 30 for (int i = 0; i < totlen; i++) ++cc[RANK[i] = (s[i] - 'a')]; 31 for (int i = 1; i < m; i++) cc[i] += cc[i - 1]; 32 for (int i = totlen - 1; i >= 0; --i) SA[--cc[RANK[i]]] = i; 33 34 for (int k = 1; k <= totlen; k <<= 1) 35 { 36 int p = 0; 37 38 for (int i = totlen - k; i < totlen; i++) 39 {//第二关键字为空的后缀放在最开头 40 r2[p++] = i; 41 } 42 for (int i = 0; i < totlen; i++) 43 {//接着放第二关键字不为空的 44 if (SA[i] >= k) r2[p++] = SA[i] - k; 45 } 46 //计数排序 47 for (int i = 0; i < m; i++) cc[i] = 0; 48 for (int i = 0; i < totlen; i++) ++cc[RANK[i]]; 49 //for (int i = 0; i < totlen; i++) ++cc[RANK[r2[i]]]; 50 for (int i = 1; i < m; i++) cc[i] += cc[i - 1]; 51 for (int i = totlen - 1; i >= 0; --i) SA[--cc[RANK[r2[i]]]] = r2[i]; 52 53 swap(RANK, r2); 54 m = 1; 55 RANK[SA[0]] = 0; 56 //r2指向旧的rank数组 57 for (int i = 1; i < totlen; i++) RANK[SA[i]] = (Cmp(r2, SA[i], SA[i - 1], k) ? m - 1 : m++); 58 59 if (m >= totlen) break; 60 } 61 } 62 void Build_Height() 63 { 64 for (int i = 0; i < totlen; i++) RANK[SA[i]] = i; 65 Height[0] = 0; 66 int k = 0; 67 for (int i = 0; i < totlen; i++) 68 { 69 if (!RANK[i]) continue; 70 int j = SA[RANK[i] - 1]; 71 if (k) k--; 72 while (s[i + k] == s[j + k]) k++; 73 Height[RANK[i]] = k; 74 } 75 } 76 77 78 79 int Judge(int x) 80 { 81 int ans = -1; 82 for (int i = 0; i < totlen; i++) 83 { 84 if (totlen - SA[i] < x)continue; 85 int tans = SA[i], cnt = 1; 86 while (i + 1 < totlen&&Height[i + 1] >= x) 87 { 88 tans = max(tans, SA[i + 1]); 89 cnt++; 90 i++; 91 } 92 if (cnt >= k) ans = max(ans, tans); 93 } 94 return ans; 95 } 96 void Solve() 97 { 98 if (Judge(1) == -1) 99 { 100 printf("none\n"); 101 return; 102 } 103 int l = 1, r = r = totlen,ans; 104 while (l <= r) 105 { 106 int mid = (l + r) / 2; 107 int tmp = Judge(mid); 108 if ( tmp!= -1) l = mid + 1,ans=tmp; 109 else r = mid - 1; 110 } 111 printf("%d %d\n", r, ans); 112 } 113 int main() 114 { 115 while (~scanf("%d", &k) && k) 116 { 117 scanf("%s", s); 118 totlen = strlen(s); 119 Build_SA(); 120 Build_Height(); 121 //for (int i = 0; i < totlen; i++) printf("%d ", SA[i]); 122 //printf("\n"); 123 //for (int i = 0; i < totlen; i++) printf("%d ", Height[i]); 124 //printf("\n"); 125 Solve(); 126 } 127 return 0; 128 }
3、HDU - 2459/POJ-3693 Maximum repetition substring
题意：求给出的字符串中，重复次数最多的连续子串，且字典序最小。
思路：后缀数组倍增算法+RMQ查询。枚举重复的长度，找到其最多出现几次。参考：http://blog.csdn.net/libin56842/article/details/46317153
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<string> 6 #include<cmath> 7 using namespace std; 8 const int maxl = 100010; 9 char s[maxl]; 10 int totlen; 11 int r2[maxl], cc[maxl], SA[maxl], RANK[maxl], Height[maxl]; 12 //r2:以第二关键字对后缀排序所得辅助数组 13 //cc：基数排序辅助数组 14 //RANK:RANK[i]表示后缀i~totlen-1(suffix[i])在所有后缀中的排名 15 //Height[i]:表示suffix[SA[i]]和suffix[SA[i-1]]的最长公共前缀 16 //SA[i]:后缀数组，满足suffix[SA[1]]<suffix[SA[2]]<……<suffix[SA[len]],即排名为i的后缀为suffix[SA[i]] 17 int minsame[maxl][20]; 18 int len[maxl]; 19 bool Cmp(int *Rank, int idx1, int idx2, int len) 20 { 21 int a1 = Rank[idx1]; 22 int b1 = Rank[idx2]; 23 int a2 = (idx1 + len >= totlen ? -1 : Rank[idx1 + len]); 24 int b2 = (idx2 + len >= totlen ? -1 : Rank[idx2 + len]); 25 return a1 == b1 && a2 == b2; 26 } 27 28 void Build_SA() 29 { 30 int m = 26; 31 32 for (int i = 0; i < m; i++) cc[i] = 0; 33 for (int i = 0; i < totlen; i++) ++cc[RANK[i] = (s[i] - 'a')]; 34 for (int i = 1; i < m; i++) cc[i] += cc[i - 1]; 35 for (int i = totlen - 1; i >= 0; --i) SA[--cc[RANK[i]]] = i; 36 37 for (int k = 1; k <= totlen; k <<= 1) 38 { 39 int p = 0; 40 41 for (int i = totlen - k; i < totlen; i++) 42 {//第二关键字为空的后缀放在开头 43 r2[p++] = i; 44 } 45 for (int i = 0; i < totlen; i++) 46 {//接着放第二关键字不为空的 47 if (SA[i] >= k) r2[p++] = SA[i] - k; 48 } 49 50 for (int i = 0; i < m; i++) cc[i] = 0; 51 for (int i = 0; i < totlen; i++) ++cc[RANK[i]]; 52 for (int i = 1; i < m; i++) cc[i] += cc[i - 1]; 53 for (int i = totlen - 1; i >= 0; --i) SA[--cc[RANK[r2[i]]]] = r2[i]; 54 55 swap(RANK, r2); 56 m = 1; 57 RANK[SA[0]] = 0; 58 for (int i = 1; i < totlen; i++) RANK[SA[i]] = (Cmp(r2, SA[i], SA[i - 1], k) ? m - 1 : m++); 59 if (m >= totlen) break; 60 61 } 62 } 63 64 void Build_Height() 65 { 66 for (int i = 0; i < totlen; i++) RANK[SA[i]] = i; 67 Height[0] = 0; 68 int k = 0; 69 for (int i = 0; i < totlen; i++) 70 { 71 if (!RANK[i]) continue; 72 int j = SA[RANK[i] - 1]; 73 if (k) k--; 74 while (s[i + k] == s[j + k]) k++; 75 Height[RANK[i]] = k; 76 } 77 } 78 void RMQ() 79 { 80 for (int i = 0; i < totlen; i++) 81 { 82 minsame[i][0] = Height[i]; 83 } 84 for (int j = 1; j < 20; j++) 85 { 86 for (int i = 0; i < totlen; i++) 87 { 88 if (i + (1 << j) - 1 < totlen) 89 { 90 minsame[i][j] = min(minsame[i][j - 1], minsame[i + (1 << (j - 1))][j - 1]); 91 } 92 } 93 } 94 } 95 int Ques(int l, int r) 96 { 97 l = RANK[l], r = RANK[r]; 98 if (l > r) 99 { 100 swap(l, r); 101 } 102 l++; 103 104 int k = 0; 105 while ((1 << (k + 1)) <= r - l + 1) k++; 106 //int k = (int)log2((double)(r - l + 1)); 107 return min(minsame[l][k], minsame[r - (1 << k) + 1][k]); 108 109 } 110 int main() 111 { 112 int Case = 1; 113 while (~scanf("%s", s)&&s[0]!='#') 114 { 115 totlen = strlen(s); 116 Build_SA(); 117 Build_Height(); 118 RMQ(); 119 //for (int i = 0; i < totlen; i++) printf("%d ", SA[i]); 120 //printf("\n"); 121 //for (int i = 0; i < totlen; i++) printf("%d ", Height[i]); 122 //printf("\n"); 123 //for (int i = 0; i < totlen; i++) printf("%d ", RANK[i]); 124 //printf("\n"); 125 //int l, r; 126 //while (~scanf("%d%d", &l, &r)) 127 //{ 128 // printf("%d\n", Ques(l, r)); 129 //} 130 int maxstep = 0;//最大重复次数 131 int cnt = 0; 132 for (int L = 1; L < totlen; L++) 133 {//枚举长度 134 for (int i = 0; i+L < totlen; i += L) 135 { 136 int k = Ques(i, i + L); 137 int t_step = k / L + 1; 138 if (i - (L - k % L) >= 0&&k%L!=0) 139 { 140 if (Ques(i - (L - k % L), i - (L - k % L) + L)>= k) t_step++; 141 } 142 if (t_step > maxstep) 143 { 144 cnt = 0; 145 maxstep = t_step; 146 len[cnt++] = L; 147 } 148 else if (t_step == maxstep) len[cnt++] = L; 149 } 150 } 151 int start, rl; 152 bool flag = true; 153 for (int i = 0; i < totlen&&flag; i++) 154 { 155 int ts = SA[i]; 156 for (int j = 0; j < cnt&&flag; j++) 157 { 158 int tl = len[j]; 159 if (Ques(ts, ts + tl) >= (maxstep - 1)*tl) 160 { 161 start = ts; 162 rl = tl * maxstep; 163 flag = false; 164 } 165 } 166 } 167 printf("Case %d: ", Case++); 168 for (int i = 0; i < rl; i++) printf("%c", s[start + i]); 169 printf("\n"); 170 } 171 172 return 0; 173 }