这道题和UVa 12206一样，求至少重复出现k次的最长字串。
首先还是二分最长字串的长度len，然后以len为边界对height数组分段，如果有一段包含超过k个后缀则符合要求。
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int maxn = 20000 + 10; 7 const int maxm = 1000000 + 10; 8 9 int s[maxn];10 int sa[maxn], height[maxn], rank[maxn];11 int t[maxn], t2[maxn], c[maxm];12 int n, k;13 14 void build_sa(int m)15 {16 int i, *x = t, *y = t2;17 for(i = 0; i < m; i++) c[i] = 0;18 for(i = 0; i < n; i++) c[x[i] = s[i]]++;19 for(i = 1; i < m; i++) c[i] += c[i - 1];20 for(i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;21 for(int k = 1; k <= n; k <<= 1)22 {23 int p = 0;24 for(i = n - k; i < n; i++) y[p++] = i;25 for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;26 for(i = 0; i < m; i++) c[i] = 0;27 for(i = 0; i < n; i++) c[x[y[i]]]++;28 for(i = 1; i < m; i++) c[i] += c[i - 1];29 for(i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];30 swap(x, y);31 p = 1; x[sa[0]] = 0;32 for(i = 1; i < n; i++)33 x[sa[i]] = y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ? p - 1 : p++;34 if(p >= n) break;35 m = p;36 }37 }38 39 void build_height()40 {41 int i, j, k = 0;42 for(i = 0; i < n; i++) rank[sa[i]] = i;43 for(i = 0; i < n; i++)44 {45 if(k) k--;46 j = sa[rank[i] - 1];47 while(s[i + k] == s[j + k]) k++;48 height[rank[i]] = k;49 }50 }51 52 bool ok(int len)53 {54 int cnt = 0;55 for(int i = 0; i < n; i++)56 {57 if(i == 0 || height[i] < len) cnt = 0;58 if(++cnt >= k) return true;59 }60 return false;61 }62 63 int main()64 {65 //freopen("in.txt", "r", stdin);66 67 scanf("%d%d", &n, &k);68 for(int i = 0; i < n; i++)69 {70 scanf("%d", &s[i]);71 s[i]++;72 }73 s[n] = 0;74 build_sa(1000002);75 build_height();76 77 int L = 1, R = n;78 while(L < R)79 {80 int M = (L + R + 1) / 2;81 if(ok(M)) L = M;82 else R = M - 1;83 }84 85 printf("%d\n", L);86 87 return 0;88 }