后缀数组初步

2015年11月18日

　　uoj模板题：

 1 #include <bits/stdc++.h>
 2 #define rep(i, a, b) for (register int i = a; i <= b; i++)
 3 #define drep(i, a, b) for (register int i = a; i >= b; i--)
 4 #define REP(i, a, b) for (int i = a; i < b; i++)
 5 #define pb push_back
 6 #define mp make_pair
 7 #define clr(x) memset(x, 0, sizeof(x))
 8 #define xx first
 9 #define yy second
10 
11 using namespace std;
12 
13 typedef long long i64;
14 typedef pair<int, int> pii;
15 const int inf = ~0U >> 1;
16 const i64 INF = ~0ULL >> 1;
17 //********************************
18 
19 const int maxn = 100005;
20 
21 char s[maxn];
22 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
23 void build_sa(int m) {
24     int *x = t, *y = t2;
25     REP(i, 0, m) c[i] = 0;
26     REP(i, 0, n) c[x[i] = s[i]]++;
27     REP(i, 1, m) c[i] += c[i - 1];
28     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
29     for (int k = 1; k <= n; k <<= 1) {
30         int p = 0;
31         REP(i, n - k, n) y[p++] = i;
32         REP(i, 0 , n) if (sa[i] >= k) y[p++] = sa[i] - k;
33 
34         REP(i, 0, m) c[i] = 0;
35         REP(i, 0, n) c[x[y[i]]]++;
36         REP(i, 1, m) c[i] += c[i - 1];
37         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
38 
39         swap(x, y);
40         p = 1; x[sa[0]] = 0;
41         REP(i, 1, n)
42             x[sa[i]] = y[sa[i - 1]]==y[sa[i]] && y[sa[i - 1] + k]==y[sa[i] + k] ? p - 1 : p++;
43         if (p >= n) break;
44         m = p;
45     }
46 }
47 
48 int rnk[maxn], height[maxn];
49 void getHeight() {
50     REP(i, 0, n) rnk[sa[i]] = i;
51     int k(0);
52     REP(i, 0, n) {
53         if (k) k--;
54         int j = sa[rnk[i] - 1];
55         while (s[i + k] == s[j + k]) k++;
56         height[rnk[i]] = k;
57     }
58 }
59 
60 int main() {
61     scanf("%s", s);
62     n = strlen(s) + 1;
63     build_sa('z' + 1);
64     REP(i, 1, n) printf("%d ", sa[i] + 1);
65     puts("");
66     getHeight();
67     REP(i, 2, n) printf("%d ", height[i]);
68     return 0;
69 }

View Code

2015年11月20日

　　poj1743 <最大不重合公共子序列长度>

　　　　给出一个数列，差分之，求出最长差分相同的序列。

　　　　首先后缀a和后缀b的LCP为height[sa[a] + 1] - height[sa[b]]的最小值，假设sa[a] < sa[b];

　　　　那么若不考虑重合，在二分答案的同时，将height数组按大于等于二分值和小于二分值分段，比如(1, 2, 3, 4, 1, 2) 用2来二分则划分为(1, (2, 3, 4), (1), (2));

　　　　再考虑重合，符合答案的情况则一定在大于二分值的每段中，只需找到每一个大于二分值的段中的最大sa和最小sa，然后Max - Min > mid 即可，>是因为差分后不能重合，若没有差分，则用>=

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define rep(i, a, b) for (int i = a; i <= b; i++)
  5 #define REP(i, a, b) for (int i = a; i < b; i++)
  6 #define drep(i, a, b) for (int i = a; i >= b; i--)
  7 #define pb push_back
  8 #define mp make_pair
  9 #define clr(x) memset(x, 0, sizeof(x))
 10 #define travel(x) for (int i = G[x]; i; i = e[i].nx)
 11 #define xx first
 12 #define yy second
 13 
 14 using namespace std;
 15 
 16 typedef long long i64;
 17 typedef pair<int, int> pii;
 18 const int inf = ~0U >> 1;
 19 const i64 INF = ~0ULL >> 1;
 20 //***************************
 21 
 22 const int maxn = 20005;
 23 
 24 int s[maxn];
 25 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
 26 void build_sa(int m) {
 27     int *x = t, *y = t2;
 28     REP(i, 0, m) c[i] = 0;
 29     REP(i, 0, n) c[x[i] = s[i]]++;
 30     REP(i, 1, m) c[i] += c[i - 1];
 31     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
 32 
 33     for (int k = 1; k <= n; k <<= 1) {
 34         int p = 0;
 35         REP(i, n - k, n) y[p++] = i;
 36         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
 37 
 38         REP(i, 0, m) c[i] = 0;
 39         REP(i, 0, n) c[x[y[i]]]++;
 40         REP(i, 1, m) c[i] += c[i - 1];
 41         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
 42 
 43         swap(x, y);
 44         p = 1, x[sa[0]] = 0;
 45         REP(i, 1, n)
 46             x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
 47         if (p >= n) break;
 48         m = p;
 49     }
 50 }
 51 
 52 int rnk[maxn], height[maxn];
 53 void buildHeight() {
 54     int k(0);
 55     REP(i, 0, n) rnk[sa[i]] = i;
 56     REP(i, 0, n) {
 57         if (k) k--;
 58         if (rnk[i] == 0) continue;
 59         int j = sa[rnk[i] - 1];
 60         while (s[i + k] == s[j + k]) k++;
 61         height[rnk[i]] = k;
 62     }
 63 }
 64 
 65 bool judge(int key) {
 66     int Min = 0x3f3f3f3f, Max = -0x3f3f3f3f;
 67     REP(i, 1, n) {
 68         if (height[i] >= key) {
 69             Min = min(Min, min(sa[i - 1], sa[i]));
 70             Max = max(Max, max(sa[i - 1], sa[i]));
 71         }
 72         else {
 73             if (Max - Min > key) return true;
 74             Min = 0x3f3f3f3f, Max = -0x3f3f3f3f;
 75         }
 76     }
 77     if (Max - Min > key) return true;
 78     else return false;
 79 }
 80 
 81 int a[maxn];
 82 int main() {
 83     while (scanf("%d", &n) && n) {
 84         REP(i, 0, n) scanf("%d", &a[i]);
 85         if (n < 10) { puts("0"); continue; }
 86         REP(i, 0, n - 1) s[i] = a[i + 1] - a[i] + 100;
 87         s[n - 1] = 0;
 88         build_sa(200), buildHeight();
 89         
 90         int low = 0, high = maxn - 1;
 91         while (low < high - 1) {
 92             int mid = low + high >> 1;
 93             if (judge(mid)) low = mid;
 94             else  high = mid;
 95         }
 96         if (low + 1 < 5) puts("0");
 97         else printf("%d
", low + 1);
 98     }
 99     return 0;
100 }

View Code

　　poj3261 <最大可重复公共子序列长度>

　　　　和上一题一样。不要忘记判judge()的最后一个！！！

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define rep(i, a, b) for (int i = a; i <= b; i++)
  5 #define drep(i, a, b) for (int i = a; i >= b; i--)
  6 #define REP(i, a, b) for (int i = a; i < b; i++)
  7 #define mp make_pair
  8 #define pb push_back
  9 #define clr(x) memset(x, 0, sizeof(x))
 10 #define xx first
 11 #define yy second
 12 
 13 using namespace std;
 14 
 15 typedef long long i64;
 16 typedef pair<int, int> pii;
 17 const int inf = ~0U >> 1;
 18 const i64 INF = ~0ULL >> 1;
 19 //*****************************
 20 
 21 const int maxn = 20005;
 22 int hsh[maxn], cd;
 23 int s[maxn], sa[maxn], t[maxn], t2[maxn], c[maxn], n;
 24 void build_sa(int m) {
 25     int *x = t, *y = t2;
 26     REP(i, 0, m) c[i] = 0;
 27     REP(i, 0, n) c[x[i] = s[i]]++;
 28     REP(i, 1, m) c[i] += c[i - 1];
 29     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
 30 
 31     for (int k = 1; k <= n; k <<= 1) {
 32         int p = 0;
 33         REP(i, n - k, n) y[p++] = i;
 34         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
 35 
 36         REP(i, 0, m) c[i] = 0;
 37         REP(i, 0, n) c[x[y[i]]]++;
 38         REP(i, 1, m) c[i] += c[i - 1];
 39         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
 40 
 41         swap(x, y);
 42         p = 1; x[sa[0]] = 0;
 43         REP(i, 1, n)
 44             x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
 45         if (p >= n) break;
 46         m = p;
 47     }
 48 }
 49 
 50 int rnk[maxn], height[maxn];
 51 void build_height() {
 52     REP(i, 0, n) rnk[sa[i]] = i;
 53     int k(0);
 54     REP(i,  0, n - 1) {
 55         if (k) k--;
 56         int j = sa[rnk[i] - 1];
 57         while (s[i + k] == s[j + k]) k++;
 58         height[rnk[i]] = k;
 59     }
 60 }
 61 
 62 bool judge(int key, int k) {
 63     int cnt(0);
 64     REP(i, 2, n) {
 65         if (height[i] >= key) cnt++;
 66         else {
 67             if (cnt + 1 >= k) return true;
 68             cnt = 0;
 69         }
 70     }
 71     if (cnt + 1 >= k) return true;
 72     else return false;
 73 }
 74 
 75 int read() {
 76     int l = 1, ret(0);
 77     char ch = getchar();
 78     while (ch < '0' || ch > '9') {if (ch == '-') l = -1; ch = getchar(); }
 79     while (ch >= '0' && ch <= '9') { ret = (ret << 1) + (ret << 3) + ch - '0'; ch = getchar(); }
 80     return l * ret;
 81 }
 82 int a[maxn];
 83 int main() {
 84     int k;
 85     scanf("%d%d", &n, &k);
 86     n++;
 87     rep(i, 1, n) scanf("%d", &a[i]), hsh[cd++] = a[i];
 88     sort(hsh, hsh + n); cd = unique(hsh, hsh + cd) - hsh;
 89     REP(i, 0, n) s[i] = lower_bound(hsh, hsh + cd, a[i + 1]) - hsh;
 90     build_sa(cd); build_height();
 91     
 92     int low = 0, high = maxn;
 93     while (low < high - 1) {
 94         int mid = low + high >> 1;
 95         if (judge(mid, k)) low = mid;
 96         else high = mid;
 97     }
 98     printf("%d
", low);
 99     return 0;
100 }

View Code

　　spoj694 <不同子序列个数>

　　　　首先后缀数组，考虑按sa的顺序依次加入考虑，每加入一个，则以它开头的子串会增加len - sa[i]个，考虑这些被加入的字符串的重复情况，因为height往上递减，所以用它和以前的重复情况不如考虑它和它 - 1的重复情况，即减去height[i];

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define rep(i, a, b) for (int i = a; i <= b; i++)
 5 #define drep(i, a, b) for (int i = a; i >= b; i--)
 6 #define REP(i, a, b) for (int i = a; i < b; i++)
 7 #define mp make_pair
 8 #define pb push_back
 9 #define clr(x) memset(x, 0, sizeof(x))
10 #define xx first
11 #define yy second
12 
13 using namespace std;
14 
15 typedef long long i64;
16 typedef pair<int, int> pii;
17 const int inf = ~0U >> 1;
18 const i64 INF = ~0ULL >> 1;
19 //*****************************
20 
21 const int maxn = 1005;
22 char s[maxn];
23 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
24 void build_sa(int m) {
25     int *x = t, *y = t2;
26     REP(i, 0, m) c[i] = 0;
27     REP(i, 0, n) c[x[i] = s[i]]++;
28     REP(i, 1, m) c[i] += c[i - 1];
29     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
30 
31     for (int k = 1; k <= n; k <<= 1) {
32         int p = 0;
33         REP(i, n - k, n) y[p++] = i;
34         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
35 
36         REP(i, 0, m) c[i] = 0;
37         REP(i, 0, n) c[x[y[i]]]++;
38         REP(i, 1, m) c[i] += c[i - 1];
39         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
40 
41         swap(x, y);
42         p = 1; x[sa[0]] = 0;
43         REP(i, 1, n)
44             x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
45         if (p >= n) break;
46         m = p;
47     }
48 }
49 
50 int rnk[maxn], height[maxn];
51 void build_height() {
52     int k(0);
53     REP(i, 0, n) rnk[sa[i]] = i;
54     REP(i, 0, n - 1) {
55         if (k) k--;
56         int j = sa[rnk[i] - 1];
57         while (s[i + k] == s[j + k]) k++;
58         height[rnk[i]] = k;
59     }
60 }
61 
62 int main() {
63     int T;
64     scanf("%d", &T);
65     while (T--) {
66         scanf("%s", s);
67         n = strlen(s) + 1;
68         build_sa('z' + 1); build_height();
69         int ans(0);
70         REP(i, 1, n) {
71             ans += n - sa[i] - 1;
72             ans -= height[i];
73         }
74         printf("%d
", ans);
75     }
76     return 0;
77 }

View Code

2015年11月22日

　　ural1297 <最长回文子串>

　　　　将原字符串翻转后接在一开始的字符串后面，用rmq查询两个字符串的LCP，依次枚举每一个点即可。记住:n总比最后一个下标大2.

  1 #include <bits/stdc++.h>
  2 #define rep(i, a, b) for (int i = a; i <= b; i++)
  3 #define drep(i, a, b) for (int i = a; i >= b; i--)
  4 #define REP(i, a, b) for (int i = a; i < b; i++)
  5 #define pb push_back
  6 #define mp make_pair
  7 #define clr(x) memset(x, 0, sizeof(x))
  8 #define xx first
  9 #define yy second
 10 using namespace std;
 11 typedef long long i64;
 12 typedef pair<int, int> pii;
 13 const int inf = ~0U>>1;
 14 const i64 INF = ~0ULL>>1;
 15 //***************************
 16 
 17 const int maxn = 600005;
 18 char s[maxn];
 19 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
 20 void build_sa(int m) {
 21     int *x = t, *y = t2;
 22     REP(i, 0, m) c[i] = 0;
 23     REP(i, 0, n) c[x[i] = s[i]]++;
 24     REP(i, 1, m) c[i] += c[i - 1];
 25     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
 26 
 27     for (int k = 1; k <= n; k <<= 1) {
 28         int p = 0;
 29         REP(i, n - k, n) y[p++] = i;
 30         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
 31 
 32         REP(i, 0, m) c[i] = 0;
 33         REP(i, 0, n) c[x[y[i]]]++;
 34         REP(i, 1, m) c[i] += c[i - 1];
 35         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
 36 
 37         swap(x, y);
 38         p = 1, x[sa[0]] = 0;
 39         REP(i, 1, n)
 40             x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
 41         if (p >= n) break;
 42         m = p;
 43     }
 44 }
 45 
 46 int rnk[maxn], height[maxn];
 47 void build_height() {
 48     REP(i, 0, n) rnk[sa[i]] = i;
 49     int k(0);
 50     REP(i, 0, n - 1) {
 51         if (k) k--;
 52         int j = sa[rnk[i] - 1];
 53         while (s[i + k] == s[j + k]) k++;
 54         height[rnk[i]] = k;
 55     }
 56 }
 57 
 58 char str[maxn];
 59 
 60 int Min[maxn][32], Log[maxn];
 61 void build_st(int lim) {
 62     Log[1] = 0;
 63     rep(i, 2, lim) {
 64         Log[i] = Log[i - 1];
 65         if (1 << Log[i] + 1 == i) Log[i]++;
 66     }
 67     drep(i, lim - 1, 1) {
 68         Min[i][0] = height[i];
 69         for (int j = 1; i + (1 << j) - 1 < lim; j++) {
 70             Min[i][j] = min(Min[i][j - 1], Min[i + (1 << j - 1)][j - 1]);
 71         }
 72     }
 73 }
 74 int query(int l, int r) {
 75     int len = r - l + 1, k = Log[len];
 76     return min(Min[l][k], Min[r - (1 << k) + 1][k]);
 77 }
 78 
 79 int main() {
 80     scanf("%s", str);
 81     n = strlen(str);
 82     memcpy(s, str, sizeof(str));
 83     s[n] = '$';
 84     rep(i, 1, n) s[n + i] = s[n - i];
 85     n++, n <<= 1;
 86     build_sa('z' + 1); build_height();
 87     build_st(n);
 88     int ans = -1, strt;
 89     for (int i = 0; str[i]; i++) {
 90         int j = n - 2 - i;
 91         int tmp = query(min(rnk[i], rnk[j]) + 1, max(rnk[i], rnk[j]));
 92         int len = (tmp << 1) - 1;
 93         if (len > ans) ans = len, strt = i - tmp + 1;
 94         j++; tmp = query(min(rnk[i], rnk[j]) + 1, max(rnk[i], rnk[j]));
 95         len = tmp << 1;
 96         if (len > ans) ans = len, strt = i - tmp;
 97     }
 98     while (ans--) putchar(s[strt++]);
 99     return 0;
100 }

View Code

　　APIO2014 Palindromes <回文子串长度 * 这个子串出现次数的最大值> TLE

　　　　这个题应该Manacher+后缀数组，Manachar后面学，，我用后缀数组统计超时了。。。

  1 #include <bits/stdc++.h>
  2 #define rep(i, a, b) for (int i = a; i <= b; i++)
  3 #define drep(i, a, b) for (int i = a; i >= b; i--)
  4 #define REP(i, a, b) for (int i = a; i < b; i++)
  5 #define pb push_back
  6 #define mp make_pair
  7 #define clr(x) memset(x, 0, sizeof(x))
  8 #define xx first
  9 #define yy second
 10 using namespace std;
 11 typedef long long i64;
 12 typedef pair<int, int> pii;
 13 const int inf = ~0U>>1;
 14 const i64 INF = ~0ULL>>1;
 15 //***************************
 16 
 17 const int maxn = 600005;
 18 char s[maxn];
 19 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
 20 void build_sa(int m) {
 21     int *x = t, *y = t2;
 22     REP(i, 0, m) c[i] = 0;
 23     REP(i, 0, n) c[x[i] = s[i]]++;
 24     REP(i, 1, m) c[i] += c[i - 1];
 25     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
 26 
 27     for (int k = 1; k <= n; k <<= 1) {
 28         int p = 0;
 29         REP(i, n - k, n) y[p++] = i;
 30         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
 31 
 32         REP(i, 0, m) c[i] = 0;
 33         REP(i, 0, n) c[x[y[i]]]++;
 34         REP(i, 1, m) c[i] += c[i - 1];
 35         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
 36 
 37         swap(x, y);
 38         p = 1, x[sa[0]] = 0;
 39         REP(i, 1, n)
 40             x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
 41         if (p >= n) break;
 42         m = p;
 43     }
 44 }
 45 
 46 int rnk[maxn], height[maxn];
 47 void build_height() {
 48     REP(i, 0, n) rnk[sa[i]] = i;
 49     int k(0);
 50     REP(i, 0, n - 1) {
 51         if (k) k--;
 52         int j = sa[rnk[i] - 1];
 53         while (s[i + k] == s[j + k]) k++;
 54         height[rnk[i]] = k;
 55     }
 56 }
 57 
 58 char str[maxn];
 59 
 60 int Min[maxn][32], Log[maxn];
 61 void build_st(int lim) {
 62     Log[1] = 0;
 63     rep(i, 2, lim) {
 64         Log[i] = Log[i - 1];
 65         if (1 << Log[i] + 1 == i) Log[i]++;
 66     }
 67     drep(i, lim - 1, 1) {
 68         Min[i][0] = height[i];
 69         for (int j = 1; i + (1 << j) - 1 < lim; j++) {
 70             Min[i][j] = min(Min[i][j - 1], Min[i + (1 << j - 1)][j - 1]);
 71         }
 72     }
 73 }
 74 int query(int l, int r) {
 75     int len = r - l + 1, k = Log[len];
 76     return min(Min[l][k], Min[r - (1 << k) + 1][k]);
 77 }
 78 
 79 int search_above(int low, int high, int len, int pos) {
 80     while (low < high - 1) {
 81         int mid = low + high >> 1;
 82         if (query(mid + 1, pos) >= len) high = mid;
 83         else  low = mid;
 84     }
 85     return high;
 86 }
 87 
 88 int search_behind(int low, int high, int len, int pos) {
 89     while (low < high - 1) {
 90         int mid = low + high >> 1;
 91         if (query(pos + 1, mid) >= len) low = mid;
 92         else high = mid;
 93     }
 94     return low;
 95 }
 96 
 97 int ans = -1;
 98 void solve(int st, int len) {
 99     while (1) {
100         int pos = rnk[st];
101         int pos1 = search_above(0, pos, len, pos);
102         int pos2 = search_behind(pos, n, len, pos);
103         ans = max(ans, (pos2 - pos1 + 1) * len >> 1);
104         len -= 2;
105         st += 1;
106         if (len <= 0) break;
107     }
108 }
109 
110 int main() {
111     scanf("%s", str);
112     n = strlen(str);
113     memcpy(s, str, sizeof(str));
114     s[n] = '$';
115     rep(i, 1, n) s[n + i] = s[n - i];
116     n++, n <<= 1;
117     build_sa('z' + 1); build_height();
118     build_st(n);
119     for (int i = 0; str[i]; i++) {
120         int j = n - 2 - i;
121         int tmp = query(min(rnk[i], rnk[j]) + 1, max(rnk[i], rnk[j]));
122         int len = (tmp << 1) - 1;
123         solve(i - tmp + 1, len);
124         j++; tmp = query(min(rnk[i], rnk[j]) + 1, max(rnk[i], rnk[j]));
125         len = tmp << 1;
126         solve(i - tmp, len);
127     }
128     printf("%d
", ans);
129     return 0;
130 }

View Code

　　poj2406 <连续重复子串> TLE

　　　　倍增后缀数组TLE...原来是KMP做的。

　　　　暴力枚举长度k，然后查询rnk[n - k]和rnk[0]的LCP，若LCP >= n - k则当前k可行。只需预先处理出所有后缀和rnk[0]的最小值即可。

 1 #include <bits/stdc++.h>
 2 #define rep(i, a, b) for (int i = a; i <= b; i++)
 3 #define drep(i, a, b) for (int i = a; i >= b; i--)
 4 #define REP(i, a, b) for (int i = a; i < b; i++)
 5 #define pb push_back
 6 #define mp make_pair
 7 #define clr(x) memset(x, 0, sizeof(x))
 8 #define xx first
 9 #define yy second
10 using namespace std;
11 typedef long long i64;
12 typedef pair<int, int> pii;
13 const int inf = ~0U>>1;
14 const i64 INF = ~0ULL>>1;
15 //***************************
16 
17 const int maxn = 1000005;
18 char s[maxn];
19 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
20 void build_sa(int m) {
21     int *x = t, *y = t2;
22     REP(i, 0, m) c[i] = 0;
23     REP(i, 0, n) c[x[i] = s[i]]++;
24     REP(i, 1, m) c[i] += c[i - 1];
25     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
26 
27     for (int k = 1; k <= n; k++) {
28         int p(0);
29         REP(i, n - k, n) y[p++] = i;
30         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
31 
32         REP(i, 0, m) c[i] = 0;
33         REP(i, 0, n) c[x[y[i]]]++;
34         REP(i, 1, m) c[i] += c[i - 1];
35         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
36 
37         swap(x, y);
38         p = 1, x[sa[0]] = 0;
39         REP(i, 1, n)
40             x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
41         if (p >= n) break;
42         m = p;
43     }
44 }
45 
46 int rnk[maxn], height[maxn];
47 void build_height() {
48     REP(i, 0, n) rnk[sa[i]] = i;
49     int k(0);
50     REP(i, 0, n - 1) {
51         if (k) k--;
52         int j = sa[rnk[i] - 1];
53         while (s[i + k] == s[j + k]) k++;
54         height[rnk[i]] = k;
55     }
56 }
57 
58 int Min[maxn];
59 int main() {
60     while (1) {
61         scanf("%s", s);
62         if (s[0] == '.') break;
63         n = strlen(s) + 1;
64         build_sa('z' + 1), build_height();
65 
66         int pos = rnk[0];
67         Min[pos - 1] = height[pos], Min[pos + 1] = height[pos + 1];
68         drep(i, pos - 2, 0) Min[i] = min(Min[i + 1], height[i + 1]);
69         REP(i, pos + 2, n) Min[i] = min(Min[i - 1], height[i]);
70 
71         int len = strlen(s);
72         rep(i, 1, len) {
73             if (len % i) continue;
74             if (Min[rnk[i]] >= len - i) {
75                 printf("%d
", len / i);
76                 break;
77             }
78         }
79     }
80     return 0;
81 }

View Code

　　poj3693 <重复次数最多的连续重复子串>

　　　　先考虑重复两遍的情况，这个子串S中的[0], [L], [L * 2],[L * 3]...中至少有相邻两个被包含，考察 S[i * l] 和 S[(i + 1) * l] 的LCP，设其值为k，若 k%l有值，则可认为LCP多匹配了k%l，也可认为是少匹配了 l - k%l，向前枚举直到不符合.

  1 #include <bits/stdc++.h>
  2 #define rep(i, a, b) for (int i = a; i <= b; i++)
  3 #define drep(i, a, b) for (int i = a; i >= b; i--)
  4 #define REP(i, a, b) for (int i = a; i < b; i++)
  5 #define pb push_back
  6 #define mp make_pair
  7 #define clr(x) memset(x, 0, sizeof(x))
  8 #define xx first
  9 #define yy second
 10 using namespace std;
 11 typedef long long i64;
 12 typedef pair<int, int> pii;
 13 const int inf = ~0U>>1;
 14 const i64 INF = ~0ULL>>1;
 15 //***************************
 16 
 17 const int maxn = 200005;
 18 char s[maxn];
 19 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
 20 void build_sa(int m) {
 21     int *x = t, *y = t2;
 22     REP(i, 0, m) c[i] = 0;
 23     REP(i, 0, n) c[x[i] = s[i]]++;
 24     REP(i, 1, m) c[i] += c[i - 1];
 25     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
 26 
 27     for (int k = 1; k <= n; k <<= 1) {
 28         int p(0);
 29         REP(i, n - k, n) y[p++] = i;
 30         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
 31 
 32         REP(i, 0, m) c[i] = 0;
 33         REP(i, 0, n) c[x[y[i]]]++;
 34         REP(i, 1, m) c[i] += c[i - 1];
 35         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
 36 
 37         swap(x, y);
 38         p = 1, x[sa[0]] = 0;
 39         REP(i, 1, n)
 40             x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
 41         if (p >= n) break;
 42         m = p;
 43     }
 44 }
 45 
 46 int rnk[maxn], height[maxn];
 47 void build_height() {
 48     REP(i, 0, n) rnk[sa[i]] = i;
 49     int k(0);
 50     REP(i, 0, n - 1) {
 51         if (k) k--;
 52         int j = sa[rnk[i] - 1];
 53         while (s[i + k] == s[j + k]) k++;
 54         height[rnk[i]] = k;
 55     }
 56 }
 57 
 58 int Min[maxn][32], Log[maxn];
 59 void build_st(int lim) {
 60     Log[1] = 0;
 61     rep(i, 2, lim) {
 62         Log[i] = Log[i - 1];
 63         if (1 << Log[i] + 1 == i) Log[i]++;
 64     }
 65     drep(i, lim, 1) {
 66         Min[i][0] = height[i];
 67         for (int j = 1; i + (1 << j) - 1 <= lim; j++)
 68             Min[i][j] = min(Min[i][j - 1], Min[i + (1 << j - 1)][j - 1]);
 69     }
 70 }
 71 int query(int l, int r) {
 72     int len = r - l + 1, k = Log[len];
 73     return min(Min[l][k], Min[r - (1 << k) + 1][k]);
 74 }
 75 
 76 int main() {
 77     int T(0);
 78     while(~scanf("%s",s) && s[0]!='#') {
 79         T++;
 80         printf("Case %d: ", T);
 81         n = strlen(s) + 1;
 82         build_sa('z' + 1), build_height();
 83         build_st(n - 1);
 84         int len = strlen(s);
 85         if (len == 1) { puts(s); return 0; }
 86         int ans = -1, st = inf, pril = 0;
 87         rep(l, 1, len / 2) {
 88             for (int i = 0; (i + 1) * l < len; i++) {
 89                 int q1 = i * l, q2 = (i + 1) * l;
 90                 int cur_ans = query(min(rnk[q1], rnk[q2]) + 1, max(rnk[q1], rnk[q2]));
 91                 int cur_st = q1;
 92                 int r = l - cur_ans % l;
 93                 cur_ans = cur_ans / l + 1;
 94                 int cnt(0);
 95                 for (int j = q1 - 1; j > q1 - l && s[j] == s[j + l] && j >= 0; j--) {
 96                     cnt++;
 97                     if (cnt == r) {
 98                         cur_ans++;
 99                         cur_st = j;
100                     }
101                     if (rnk[j] < rnk[cur_st]) cur_st = j;
102                 }
103                 if (cur_ans > ans || cur_ans == ans && rnk[cur_st] < rnk[st]) {
104                     ans = cur_ans;
105                     st = cur_st;
106                     pril = l;
107                 }
108             }
109         }
110         int pri = ans * pril;
111         for (int i = st, j = 0; j < pri; j++) printf("%c", s[i + j]);
112         puts("");
113     }
114     return 0;
115 }

View Code

2015年11月23日

　　spoj687 <重复次数最多的连续子串长度>

　　　　和上一道题一样，只是不用一位一位往前移动了，少了 l - (k % l) 的值，所以在枚举相邻的i时，也向前l-k%l位，查询LCP即可。

  1 #include <bits/stdc++.h>
  2 #define rep(i, a, b) for (register int i = a; i <= b; i++)
  3 #define drep(i, a, b) for (int i = a; i >= b; i--)
  4 #define REP(i, a, b) for (int i = a; i < b; i++)
  5 #define pb push_back
  6 #define mp make_pair
  7 #define clr(x) memset(x, 0, sizeof(x))
  8 #define xx first
  9 #define yy second
 10 using namespace std;
 11 typedef long long i64;
 12 typedef pair<int, int> pii;
 13 const int inf = 0x3f3f3f3f;
 14 const i64 INF = ~0ULL>>1;
 15 //***************************
 16 
 17 const int maxn = 50005;
 18 char s[maxn];
 19 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
 20 void build_sa(int m) {
 21     int *x = t, *y = t2;
 22     REP(i, 0, m) c[i] = 0;
 23     REP(i, 0, n) c[x[i] = s[i]]++;
 24     REP(i, 1, m) c[i] += c[i - 1];
 25     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
 26 
 27     for (int k = 1; k <= n; k <<= 1) {
 28         int p(0);
 29         REP(i, n - k, n) y[p++] = i;
 30         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
 31 
 32         REP(i, 0, m) c[i] = 0;
 33         REP(i, 0, n) c[x[y[i]]]++;
 34         REP(i, 1, m) c[i] += c[i - 1];
 35         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
 36 
 37         swap(x, y);
 38         p = 1, x[sa[0]] = 0;
 39         REP(i, 1, n)
 40             x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
 41         if (p >= n) break;
 42         m = p;
 43     }
 44 }
 45 
 46 int rnk[maxn], height[maxn];
 47 void build_height() {
 48     REP(i, 0, n) rnk[sa[i]] = i;
 49     int k(0);
 50     REP(i, 0, n - 1) {
 51         if (k) k--;
 52         int j = sa[rnk[i] - 1];
 53         while (s[i + k] == s[j + k]) k++;
 54         height[rnk[i]] = k;
 55     }
 56 }
 57 
 58 int Min[maxn][32], Log[maxn];
 59 void build_st(int lim) {
 60     Log[1] = 0;
 61     rep(i, 2, lim) {
 62         Log[i] = Log[i - 1];
 63         if (1 << Log[i] + 1 == i) Log[i]++;
 64     }
 65     drep(i, lim, 1) {
 66         Min[i][0] = height[i];
 67         for (int j = 1; i + (1 << j) - 1 <= lim; j++) 
 68             Min[i][j] = min(Min[i][j - 1], Min[i + (1 << j - 1)][j - 1]);
 69     }
 70 }
 71 int query(int l, int r) {
 72     int len = r - l + 1, k = Log[len];
 73     return min(Min[l][k], Min[r - (1 << k) + 1][k]);
 74 }
 75 
 76 char ch[5];
 77 int main() {
 78     int T;
 79     scanf("%d", &T);
 80     while (T--) {
 81         scanf("%d", &n);
 82         REP(i, 0, n) { scanf("%s", ch); s[i] = ch[0]; }
 83         n++;
 84         build_sa('z' + 1), build_height();
 85         build_st(n - 1);
 86         int len = n - 1;
 87         int ans = -1;
 88         rep(l, 1, len >> 1) {
 89             for (int i = 0; (i + 1) * l < len; i++) {
 90                 int LCP = query(min(rnk[i * l], rnk[(i + 1) * l]) + 1, max(rnk[i * l], rnk[(i + 1) * l]));
 91                 ans = max(ans, LCP / l + 1);
 92                 int q1 = i * l - (l - LCP % l);
 93                 if (q1 < 0) continue;
 94                 LCP = query(min(rnk[q1], rnk[q1 + l]) + 1, max(rnk[q1], rnk[q1 + l]));
 95                 ans = max(ans, LCP / l + 1);
 96             }
 97         }
 98         if (ans == -1) ans = 1;
 99         printf("%d
", ans);
100     }
101 }

View Code

2015年11月24日

　　poj2774 <两个字符串的最长公共子串长度>

　　　　首先把两个字符串拼在一起，观察height数组，sa数组中排名相邻的两个字符串若不同属于一个字符串，那么这个height被纳入考虑。

　　　　不相邻的不同属于一个字符串的不需要考虑，假设字符串a排名靠前，字符串b排名靠后，考虑b串，加入b串上面和它不同属于一个串，那么LCP(a, b) 没有LCP(b - 1, b)优；假如b - 1这个串和b同属于一个串，那么LCP(a, b) 没有 LCP(a, b - 1)优，所以只需要考虑相邻的即可。

 1 #include <bits/stdc++.h>
 2 #define rep(i, a, b) for (register int i = a; i <= b; i++)
 3 #define drep(i, a, b) for (int i = a; i >= b; i--)
 4 #define REP(i, a, b) for (int i = a; i < b; i++)
 5 #define pb push_back
 6 #define mp make_pair
 7 #define clr(x) memset(x, 0, sizeof(x))
 8 #define xx first
 9 #define yy second
10 using namespace std;
11 typedef long long i64;
12 typedef pair<int, int> pii;
13 const int inf = 0x3f3f3f3f;
14 const i64 INF = ~0ULL>>1;
15 //***************************
16 
17 const int maxn = 200005;
18 char s[maxn];
19 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
20 void build_sa(int m) {
21     int *x = t, *y = t2;
22     REP(i, 0, m) c[i] = 0;
23     REP(i, 0, n) c[x[i] = s[i]]++;
24     REP(i, 1, m) c[i] += c[i - 1];
25     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
26 
27     for (int k = 1; k <= n; k <<= 1) {
28         int p(0);
29         REP(i, n - k, n) y[p++] = i;
30         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
31 
32         REP(i, 0, m) c[i] = 0;
33         REP(i, 0, n) c[x[y[i]]]++;
34         REP(i, 1, m) c[i] += c[i - 1];
35         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
36 
37         swap(x, y);
38         p = 1; x[sa[0]] = 0;
39         REP(i, 1, n)
40             x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
41         if (p >= n) break;
42         m = p;
43     }
44 }
45 
46 int rnk[maxn], height[maxn];
47 void build_height() {
48     REP(i, 0, n) rnk[sa[i]] = i;
49     int k(0);
50     REP(i, 0, n - 1) {
51         if (k) k--;
52         int j = sa[rnk[i] - 1];
53         while (s[i + k] == s[j + k]) k++;
54         height[rnk[i]] = k;
55     }
56 }
57 
58 char str[maxn >> 1];
59 int main() {
60     scanf("%s", str);
61     memcpy(s, str, sizeof(str));
62     int cur = strlen(str);
63     int k = cur;
64     scanf("%s", str);
65     s[cur++] = '$';
66     for (int i = 0; str[i]; i++) s[cur++] = str[i];
67     n = cur + 1;
68     build_sa('z' + 1); build_height();
69     int ans = -1;
70     REP(i, 1, n) {
71         int l = sa[i - 1], r = sa[i];
72         if (l > r) swap(l, r);
73         if (l < k && r > k) ans = max(ans, height[i]);
74     }
75     printf("%d
", ans);
76     return 0;
77 }

View Code

　　ural1517 <两个字符串最长公共子串长度>

　　　　和上一道题一样，不再赘述。

 1 #include <bits/stdc++.h>
 2 #define rep(i, a, b) for (register int i = a; i <= b; i++)
 3 #define drep(i, a, b) for (int i = a; i >= b; i--)
 4 #define REP(i, a, b) for (int i = a; i < b; i++)
 5 #define pb push_back
 6 #define mp make_pair
 7 #define clr(x) memset(x, 0, sizeof(x))
 8 #define xx first
 9 #define yy second
10 using namespace std;
11 typedef long long i64;
12 typedef pair<int, int> pii;
13 const int inf = 0x3f3f3f3f;
14 const i64 INF = ~0ULL>>1;
15 //***************************
16 
17 const int maxn = 200005;
18 char s[maxn];
19 int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
20 void build_sa(int m) {
21     int *x = t, *y = t2;
22     REP(i, 0, m) c[i] = 0;
23     REP(i, 0, n) c[x[i] = s[i]]++;
24     REP(i, 1, m) c[i] += c[i - 1];
25     drep(i, n - 1, 0) sa[--c[x[i]]] = i;
26 
27     for (int k = 1; k <= n; k <<= 1) {
28         int p(0);
29         REP(i, n - k, n) y[p++] = i;
30         REP(i, 0, n) if (sa[i] >= k) y[p++] = sa[i] - k;
31 
32         REP(i, 0, m) c[i] = 0;
33         REP(i, 0, n) c[x[y[i]]]++;
34         REP(i, 1, m) c[i] += c[i - 1];
35         drep(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
36 
37         swap(x, y);
38         p = 1; x[sa[0]] = 0;
39         REP(i, 1, n)
40             x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
41         if (p >= n) break;
42         m = p;
43     }
44 }
45 
46 int rnk[maxn], height[maxn];
47 void build_height() {
48     REP(i, 0, n) rnk[sa[i]] = i;
49     int k(0);
50     REP(i, 0, n - 1) {
51         if (k) k--;
52         int j = sa[rnk[i] - 1];
53         while (s[i + k] == s[j + k]) k++;
54         height[rnk[i]] = k;
55     }
56 }
57 
58 int main() {
59     int len;
60     scanf("%d", &len);
61     scanf("%s", s);
62     s[len] = '$';
63     scanf("%s", s + len + 1);
64     n = (len << 1) + 2;
65     build_sa('z' + 1), build_height();
66     int ans = -1, st;
67     REP(i, 1, n) {
68         int q1 = sa[i], q2 = sa[i - 1];
69         if (q1 > q2) swap(q1, q2);
70         if (q1 < len && q2 > len) {
71             if (height[i] > ans) ans = height[i], st = q1;
72         }
73     }
74     while (ans--) putchar(s[st++]);
75     return 0;
76 }

View Code