題目鏈接

思路

• 如何求一個(gè)串中的最大重復(fù)次數(shù)？
  枚舉循環(huán)節(jié)的大小，判斷它是否合法。
• 如何快速判斷循環(huán)節(jié)合法？
  $LCP($原串, 原串$?$循環(huán)節(jié)$)$是否完全匹配。
• 如何快速求串$A$和串$B$的$LCP$？
  $LCP=Rank[A]$到$Rank[B]$之間的最小值。

當(dāng)我們知道如何求一個(gè)串的最大重復(fù)次數(shù)之后，再來(lái)看這個(gè)問(wèn)題：如何求一個(gè)串中重復(fù)次數(shù)最多的字符串，我們也可以枚舉循環(huán)節(jié)的長(zhǎng)度，然后枚舉起始位置進(jìn)行求解，問(wèn)題就轉(zhuǎn)化為上面的問(wèn)題了。假設(shè)當(dāng)前位置是$pos$，枚舉的長(zhǎng)度是$len，ans=max(ans,\frac{LCP(pos,pos+len)}{len}+1)$，假設(shè)當(dāng)前位置匹配，看后面還能匹配多少個(gè)長(zhǎng)度為$len$的串。復(fù)雜度：$O(n^2)$

優(yōu)化：枚舉長(zhǎng)度是必須的但是枚舉位置不必一位一位的枚舉，每次枚舉$len$的倍數(shù)即可。

• 最優(yōu)串在$len$的倍數(shù)上，枚舉的剛好是答案。
• 最優(yōu)串不在$len$的倍數(shù)上，枚舉的時(shí)候必定會(huì)有個(gè)位置距離最優(yōu)串$X$右邊最近的$pos$，令$tmp=LCP(pos,pos+len)$這是后最優(yōu)解就是$LCP(pos?len+tmp\%len，pos+tmp\%len)=LCP(X，X+len)$

復(fù)雜度分析：每次枚舉位置是$i$的倍數(shù)，$O(\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+...+\frac{n}{n})=O(nlogn)$

#include <bits/stdc++.h> #define LL long long #define P pair<int, int> #define lowbit(x) (x & -x) #define mem(a, b) memset(a, b, sizeof(a)) #define mid ((l + r) >> 1) #define lc rt<<1 #define rc rt<<1|1 #define endl '\n' const int maxn = 1e5 + 5; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; int cntA[maxn], cntB[maxn], A[maxn], B[maxn]; int Sa[maxn], tsa[maxn], height[maxn], Rank[maxn]; char s[maxn]; int n; void SuffixArray () {for (int i = 0; i < 1000; ++i) cntA[i] = 0;for (int i = 1; i <= n; ++i) cntA[(int)s[i]]++;for (int i = 1; i < 1000; ++i) cntA[i] += cntA[i-1];for (int i = n; i >= 1; --i) Sa[ cntA[(int)s[i]]-- ] = i;Rank[ Sa[1] ] = 1;for (int i = 2; i <= n; ++i) {Rank[Sa[i]] = Rank[Sa[i-1]];if (s[Sa[i]] != s[Sa[i-1]]) Rank[Sa[i]]++;}for (int l = 1; Rank[Sa[n]] < n; l <<= 1) {for (int i = 0; i <= n; ++i) cntA[i] = 0;for (int i = 0; i <= n; ++i) cntB[i] = 0;for (int i = 1; i <= n; ++i) {cntA[ A[i] = Rank[i] ]++;cntB[ B[i] = (i + l <= n) ? Rank[i+l] : 0]++;}for (int i = 1; i <= n; ++i) cntB[i] += cntB[i-1];for (int i = n; i >= 1; --i) tsa[ cntB[B[i]]-- ] = i;for (int i = 1; i <= n; ++i) cntA[i] += cntA[i-1];for (int i = n; i >= 1; --i) Sa[ cntA[A[tsa[i]]]-- ] = tsa[i];Rank[ Sa[1] ] = 1;for (int i = 2; i <= n; ++i) {Rank[Sa[i]] = Rank[Sa[i-1]];if (A[Sa[i]] != A[Sa[i-1]] || B[Sa[i]] != B[Sa[i-1]]) Rank[Sa[i]]++;}}for (int i = 1, j = 0; i <= n; ++i) {if (j) --j;int tmp = Sa[Rank[i] - 1];while (i + j <= n && tmp + j <= n && s[i+j] == s[tmp+j]) ++j;height[Rank[i]] = j;} } int dp[maxn][20]; void ST(int n) {for (int i = 1; i <= n; ++i) {dp[i][0] = height[i];}for (int j = 1; j <= log2(n); ++j) {for (int i = 1; i + (1 << j) - 1 <= n; ++i) {dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);}} } int RMQ(int l, int r) {int len = r - l + 1;int x = log2(len);return min(dp[l][x], dp[r - (1 << x) + 1][x]); }int lcp(int x, int y) {int l = Rank[x];int r = Rank[y];if (l > r) swap(l, r);return RMQ(l+1, r); } int main () {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);s[0] = ' ';scanf("%s", s+1);n = strlen(s) - 1;SuffixArray();ST(n);int ans = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j + i <= n; j += i) {int tmp = lcp(j, i + j);ans = max(ans, tmp / i + 1);if (j - i + tmp % i >= 1) {ans = max(ans, lcp(j-i+tmp%i, j+tmp%i) / i + 1);}}}cout << ans << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的#1419 : 后缀数组四·重复旋律4 (重复次数最多的连续字串)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。