乐曲主题Musical Themes

秒速五厘米 2021-12-24 16:34 253阅读 0赞

SA例题

[题面][Link 1]

对于串 \\(S\\) 的两个子串 \\(A\\) 和 \\(B\\) ，满足 \\(k = |A| = |B|\\)，\\(\\exists c \\forall i\\, a\_i + c=b\_i\\)，且 \\(A\\) 和 \\(B\\) 在原串中没有重叠，求最大的满足条件的 \\(k\\)

先考虑 \\(\\forall i\\, a\_i=b\_i\\) 的情况，二分 \\(k\\) ，如果在\\(height\\)上存在一段满足 \\(\\forall L \\le i \\le R \\,height\_i\\ge k\\)，且存在 \\(SA\[p\_1\]-SA\[p\_2\] \\ge k\\)，说明 \\(k\\) 满足条件

接下来将上述做法用在原数组的差分数组上即可，注意判定时条件要改为\\(SA\[p\_1\]-SA\[p\_2\] > k\\)，且要在第一个字符前添加特殊字符，否则判定时可能出问题

#include<cstdio> using namespace std; const int MAXN = 5001; int str[MAXN], sa[MAXN], rank[MAXN], ht[MAXN], buc[MAXN]; void Swap(int*& a, int*& b){ int *tmp = a; a = b; b = tmp; } void getSA(int s[], int len){ int *rk = rank, *tp = ht; int crd = 180, p; for (int i = 1; i <= len; ++i) rk[i] = s[i], tp[i] = i; for (int i = 0; i <= crd; ++i) buc[i] = 0; for (int i = 1; i <= len; ++i) ++buc[rk[i]]; for (int i = 1; i <= crd; ++i) buc[i] += buc[i - 1]; for (int i = len; i >= 1; --i) sa[buc[rk[tp[i]]]--] = tp[i]; for (int w = 1; p != len; w <<= 1, crd = p){ p = 0; for (int i = len - w + 1; i <= len; ++i) tp[++p] = i; for (int i = 1; i <= len; ++i) if (sa[i] > w) tp[++p] = sa[i] - w; for (int i = 0; i <= crd; ++i) buc[i] = 0; for (int i = 1; i <= len; ++i) ++buc[rk[i]]; for (int i = 1; i <= crd; ++i) buc[i] += buc[i - 1]; for (int i = len; i >= 1; --i) sa[buc[rk[tp[i]]]--] = tp[i]; Swap(rk, tp); rk[sa[1]] = p = 1; for (int i = 2; i <= len; ++i) rk[sa[i]] = tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w] ? p : ++p; } for (int i = 1; i <= len; ++i) rank[sa[i]] = i; } void getHeight(int s[], int len){ ht[1] = 0; for (int i = 1, j = 0, pos; i <= len; ++i, --j){ if (rank[i] == 1) continue; if (j < 0) j = 0; pos = sa[rank[i] - 1]; while (s[i + j] == s[pos + j] && i + j <= len && pos + j <= len) ++j; ht[rank[i]] = j; } } bool judge(int k, int len){ int lp, rp; for (int i = 1, j; i < len;){ if (ht[i + 1] >= k){ lp = rp = sa[i]; j = i + 1; while (ht[j] >= k && j <= len){ if (sa[j] < lp) lp = sa[j]; if (sa[j] > rp) rp = sa[j]; ++j; } if (rp - lp > k) return 1; i = j; } else ++i; } return 0; } int main(){ int slen; scanf("%d", &slen); for (int i = 1, pre = 89, tmp; i <= slen; ++i){ scanf("%d", &tmp); str[i] = tmp - pre + 89; pre = tmp; } getSA(str, slen); getHeight(str, slen); int L = 1, R = slen >> 1, mid; while (L + 1 < R){ mid = L + R >> 1; if (judge(mid, slen)) L = mid; else R = mid; } int ans; if (judge(R, slen)) ans = R; else ans = L; if (ans < 4) printf("0"); else printf("%d", ans + 1); return 0; }

转载于:https://www.cnblogs.com/0xfffe/p/10542838.html

[Link 1]: https://www.luogu.org/problemnew/show/P2743