【HDOJ】4080 Stammering Aliens

1. 题目描述
给定一个长为$n in [1, 4000]$的字符串，求其中长度最长的子串，并且该子串在原串中出现至少$m$次，并求最右起始位置。

2. 基本思路
两种方法：二分+后缀数组，或者二分+哈希。
（1）二分+后缀数组
对子串长度进行二分，若不同后缀的公共前缀超过这个值，则对计数值累加。若计数值超过m，则证明这个公共前缀是有效的，计数过程中同时维护pos（最右边界），从而更新rpos。

（2）二分+哈希
仍然是对长度进行二分，然后枚举其实位置计算该长度的子串的哈希值，排序后，计算，超过m表示是有效的子串，从而更新最右位置。哈希采用LCP哈希。

3. 代码
（1）后缀数组

  1 /* 4080 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 const int maxn = 40005;
 44 char s[maxn];
 45 int a[maxn];
 46 int height[maxn], sa[maxn], rrank[maxn];
 47 int wa[maxn], wb[maxn], wc[maxn], wv[maxn];
 48 int rpos, m;
 49 
 50 bool cmp(int *r, int a, int b, int l) {
 51     return r[a]==r[b] && r[a+l]==r[b+l];
 52 }
 53 
 54 void da(int *r, int *sa, int n, int m) {
 55     int i, j, *x=wa, *y=wb, *t, p;
 56 
 57     for (i=0; i<m; ++i) wc[i] = 0;
 58     for (i=0; i<n; ++i) wc[x[i]=r[i]]++;
 59     for (i=1; i<m; ++i) wc[i] += wc[i-1];
 60     for (i=n-1; i>=0; --i) sa[--wc[x[i]]] = i;
 61     for (j=1,p=1; p<n; j*=2, m=p) {
 62         for (p=0, i=n-j; i<n; ++i) y[p++] = i;
 63         for (i=0; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
 64         for (i=0; i<n; ++i) wv[i] = x[y[i]];
 65         for (i=0; i<m; ++i) wc[i] = 0;
 66         for (i=0; i<n; ++i) wc[wv[i]]++;
 67         for (i=1; i<m; ++i) wc[i] += wc[i-1];
 68         for (i=n-1; i>=0; --i) sa[--wc[wv[i]]] = y[i];
 69         for (t=x,x=y,y=t,x[sa[0]]=0,p=1,i=1; i<n; ++i)
 70             x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++;
 71     }
 72 }
 73 
 74 void calheight(int *r, int *sa, int n) {
 75     int i, j, k = 0;
 76 
 77     for (i=1; i<=n; ++i) rrank[sa[i]] = i;
 78     for (i=0; i<n; height[rrank[i++]]=k)
 79     for (k?k--:0, j=sa[rrank[i]-1]; r[j+k]==r[i+k]; ++k) ;
 80 }
 81 
 82 void printSa(int n) {
 83     for (int i=1; i<=n; ++i)
 84         printf("%d ", sa[i]);
 85     putchar('
');
 86 }
 87 
 88 void printHeight(int n) {
 89     for (int i=1; i<=n; ++i)
 90         printf("%d ", height[i]);
 91     putchar('
');
 92 }
 93 
 94 bool judge(int bound, int n) {
 95     int cnt = 1, pos = -1;
 96 
 97     rpos = -1;
 98     rep(i, 1, n+1) {
 99         if (height[i] >= bound) {
100             pos = max(pos, sa[i]);
101             ++cnt;
102         } else {
103             if (cnt >= m)
104                 rpos = max(pos, rpos);
105             pos = sa[i];
106             cnt = 1;
107         }
108     }
109     if (cnt >= m)
110         rpos = max(pos, rpos);
111 
112     return rpos!=-1;
113 }
114 
115 void solve() {
116     int n;
117 
118     for (int i=0; ; ++i) {
119         if (s[i] == '') {
120             n = i;
121             break;
122         }
123         a[i] = s[i] - 'a' + 1;
124     }
125     a[n] = 0;
126     if (m == 1) {
127         printf("%d 0
", n);
128         return ;
129     }
130 
131     da(a, sa, n+1, 30);
132     calheight(a, sa, n);
133 
134     int l = 1, r = n, mid;
135     int ans = 0, ansp;
136 
137     while (l <= r) {
138         mid = (l + r) >> 1;
139         if (judge(mid, n)) {
140             ans = mid;
141             ansp = rpos;
142             l = mid + 1;
143         } else {
144             r = mid - 1;
145         }
146     }
147 
148     if (ans)
149         printf("%d %d
", ans, ansp);
150     else
151         puts("none");
152 }
153 
154 int main() {
155     ios::sync_with_stdio(false);
156     #ifndef ONLINE_JUDGE
157         freopen("data.in", "r", stdin);
158         freopen("data.out", "w", stdout);
159     #endif
160 
161     while (scanf("%d", &m)!=EOF && m) {
162         scanf("%s", s);
163         solve();
164     }
165 
166     #ifndef ONLINE_JUDGE
167         printf("time = %d.
", (int)clock());
168     #endif
169 
170     return 0;
171 }

（2）哈希

  1 /* 4080 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 //#pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 
 44 #define ULL unsigned __int64
 45 
 46 const int MOD = 754283;
 47 const int maxn = 40005;
 48 ULL H[maxn], base[maxn];
 49 ULL Hash[maxn];
 50 int pos[maxn];
 51 char s[maxn];
 52 int c[26];
 53 int m, len;
 54 int rp;
 55 
 56 void init() {
 57     base[0] = 1;
 58     rep(i, 1, maxn)
 59         base[i] = base[i-1] * MOD;
 60 }
 61 
 62 bool comp(const int& a, const int& b) {
 63     if (Hash[a] == Hash[b])
 64         return a<b;
 65     return Hash[a] < Hash[b];
 66 }
 67 
 68 bool judge(int l) {
 69     int n = len - l + 1;
 70     for (int i=0; i<n; ++i) {
 71         pos[i] = i;
 72         Hash[i] = H[i] - H[i+l] * base[l];
 73     }
 74 
 75     sort(pos, pos+n, comp);
 76 
 77     int i = 0;
 78     rp = -1;
 79     while (i < n) {
 80         int j = i++;
 81         while (i<n && Hash[pos[i]]==Hash[pos[j]])
 82             ++i;
 83         if (i-j >= m)
 84             rp = max(rp, pos[i-1]);
 85     }
 86 
 87     return rp >= 0;
 88 }
 89 
 90 void solve() {
 91     len = strlen(s) ;
 92 
 93     memset(c, 0, sizeof(c));
 94     rep(i, 0, len)
 95         ++c[s[i]-'a'];
 96     H[len] = 0;
 97     per(i, 0, len)
 98         H[i] = H[i+1] * MOD + s[i]-'a';
 99 
100     bool flag = false;
101 
102     rep(i, 0, 26) {
103         if (c[i] >= m) {
104             flag = true;
105             break;
106         }
107     }
108 
109     if (!flag) {
110         puts("none");
111         return ;
112     }
113 
114     int ans = 1, ansp = -1;
115     int l = 1, r = len, mid;
116 
117     while (l <= r) {
118         mid = (l + r) >> 1;
119         if (judge(mid)) {
120             ans = mid;
121             ansp = rp;
122             l = mid + 1;
123         } else {
124             r = mid - 1;
125         }
126     }
127 
128     printf("%d %d
", ans, ansp);
129 }
130 
131 int main() {
132     ios::sync_with_stdio(false);
133     #ifndef ONLINE_JUDGE
134         freopen("data.in", "r", stdin);
135         freopen("data.out", "w", stdout);
136     #endif
137 
138     init();
139     while (scanf("%d", &m)!=EOF && m) {
140         scanf("%s", s);
141         solve();
142     }
143 
144 
145     #ifndef ONLINE_JUDGE
146         printf("time = %d.
", (int)clock());
147     #endif
148 
149     return 0;
150 }