?

題目傳送門

題意：訓練指南P225

分析：二分尋找長度，用hash值來比較長度為L的字串是否相等。

#include <bits/stdc++.h> using namespace std;typedef unsigned long long ull; const int N = 4e4 + 5; const int x = 123; ull H[N], _hash[N], xp[N]; int rk[N]; char str[N]; int m;void get_hash(char *s, int len) {H[len] = 0;for (int i=len-1; i>=0; --i) {H[i] = H[i+1] * x + (s[i] - 'a');}xp[0] = 1;for (int i=1; i<len; ++i) {xp[i] = xp[i-1] * x;} }bool cmp(const int &a, const int &b) {return (_hash[a] < _hash[b] || (_hash[a] == _hash[b] && a < b)); }int check(int L, int len) {int cnt = 0, pos = -1, c = 0;for (int i=0; i<len-L+1; ++i) {rk[i] = i;_hash[i] = H[i] - H[i+L] * xp[L];}sort (rk, rk+len-L+1, cmp);for (int i=0; i<len-L+1; ++i) {if (i == 0 || _hash[rk[i]] != _hash[rk[i-1]]) c = 0;if (++c >= m) pos = max (pos, rk[i]);}return pos; }int main(void) {while (scanf ("%d", &m) == 1) {if (!m) break;scanf ("%s", &str);int len = strlen (str);get_hash (str, len);if (check (1, len) == -1) puts ("none");else {int l = 1, r = len + 1;while (r - l > 1) {int mid = l + r >> 1;if (check (mid, len) >= 0) l = mid;else r = mid;}printf ("%d %d\n", l, check (l, len));}}return 0; }

?

后綴數組也可以求解，具體就是二分答案，height數組分組判斷是否滿足存在題意的解，并使最優。（m=1時特判處理）

#include <bits/stdc++.h>const int N = 4e4 + 5; int sa[N], rank[N], height[N]; int ws[N], wa[N], wb[N]; char s[N];bool cmp(int *r, int a, int b, int l) {return (r[a] == r[b] && r[a+l] == r[b+l]); } void DA(char *r, int n, int m = 128) {int i, j, p, *x = wa, *y = wb;for (i=0; i<m; ++i) ws[i] = 0;for (i=0; i<n; ++i) ws[x[i]=r[i]]++;for (i=1; i<m; ++i) ws[i] += ws[i-1];for (i=n-1; i>=0; --i) sa[--ws[x[i]]] = i;for (j=1, p=1; p<n; j<<=1, m=p) {for (p=0, i=n-j; i<n; ++i) y[p++] = i;for (i=0; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;for (i=0; i<m; ++i) ws[i] = 0;for (i=0; i<n; ++i) ws[x[y[i]]]++;for (i=1; i<m; ++i) ws[i] += ws[i-1];for (i=n-1; i>=0; --i) sa[--ws[x[y[i]]]] = y[i];std::swap (x, y);for (p=1, x[sa[0]]=0, i=1; i<n; ++i) {x[sa[i]] = cmp (y, sa[i-1], sa[i], j) ? p - 1 : p++;}} } void calc_height(char *r, int *sa, int n) {int i, j, k = 0;for (i=1; i<=n; ++i) rank[sa[i]] = i;for (i=0; i<n; ++i) {if (k) k--;j = sa[rank[i]-1];while (r[i+k] == r[j+k]) k++;height[rank[i]] = k;} }int m; int check(int len, int n) {int p = -1;int cnt = 0, ret = -1;for (int i=1; i<=n; ++i) {if (height[i] >= len) {if (p == -1) {p = std::max (sa[i-1], sa[i]);} else {p = std::max (p, std::max (sa[i-1], sa[i]));}cnt++;if (cnt + 1 >= m) {ret = std::max (ret, p);}} else {p = -1;cnt = 0;}}return ret; }int main() {while (scanf ("%d", &m) == 1) {if (!m) break;scanf ("%s", s);int n = strlen (s);if (m == 1) {printf ("%d %d\n", n, 0);continue;}DA (s, n + 1);calc_height (s, sa, n);int best = 0, pos = -1;int left = 0, right = n;while (left <= right) {int mid = left + right >> 1;int res = check (mid, n);if (res != -1) {if (best < mid) {best = mid;pos = res;} else if (mid > 0 && best == mid && pos < res) {pos = res;}left = mid + 1;} else {right = mid - 1;}}if (pos == -1) {puts ("none");} else {printf ("%d %d\n", best, pos);}}return 0; }

　　

轉載于:https://www.cnblogs.com/Running-Time/p/5123779.html

總結

以上是生活随笔為你收集整理的Hash(LCP) || 后缀数组 LA 4513 Stammering Aliens的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。