題目鏈接

題意

求字符串$S$中滿足子串可以復(fù)制$K$次得到的字串的數(shù)量，不位置字串相同的字符串分開計(jì)算

思路

看題解補(bǔ)完的這道題
枚舉循環(huán)節(jié)的長(zhǎng)度$X$，從頭找到字符串$S$中連續(xù)出現(xiàn)循環(huán)節(jié)的最多的字串，假設(shè)當(dāng)前求得的區(qū)間是$[L,R]$，$lcp(R+1,L)$即為字串向后可以擴(kuò)展的長(zhǎng)度（長(zhǎng)度小于$X$），相反求向前可以擴(kuò)展的位置。這樣每次可以得到循環(huán)節(jié)為$X$的最長(zhǎng)的連續(xù)區(qū)間，每次累計(jì)答案即可

#include <bits/stdc++.h> const int maxn = 1e6 + 5; using namespace std; struct SuffixArray{ // 下標(biāo)int cntA[maxn], cntB[maxn], A[maxn], B[maxn];int Sa[maxn], tsa[maxn], height[maxn], Rank[maxn];int n, dp[maxn][21];void init(char *buf, int len) { // 預(yù)處理，sa，rank，heightn = len;for (int i = 0; i < 128; ++i) cntA[i] = 0;for (int i = 1; i <= n; ++i) cntA[(int)buf[i]]++;for (int i = 1; i < 128; ++i) cntA[i] += cntA[i-1];for (int i = n; i >= 1; --i) Sa[ cntA[(int)buf[i]]-- ] = i;Rank[ Sa[1] ] = 1;for (int i = 2; i <= n; ++i) {Rank[Sa[i]] = Rank[Sa[i-1]];if (buf[Sa[i]] != buf[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 && buf[i+j] == buf[tmp+j]) ++j;height[Rank[i]] = j;}}void st() {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) { // 最長(zhǎng)公共前綴int l = Rank[x];int r = Rank[y];if (l > r) swap(l, r);return rmq(l+1, r);} }L, R; int work(int l, int r, int p, int len, int k) { // 計(jì)算前后綴，前后擴(kuò)展，累計(jì)答案int rt = L.lcp(l, r+1); // 向右擴(kuò)展int lt = R.lcp(len+1-r, len+1-l+1); // 向前擴(kuò)展r += rt;l -= lt;return max(0, r-l+1 - k*p + 1); // 返回kp的個(gè)數(shù) } char s[maxn], t[maxn]; int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T;scanf("%d", &T);while (T--) {int k;long long ans = 0;scanf("%d%s", &k, t+1);int len = strlen(t+1);if (k == 1) {ans = 1ll * (1 + len) * len / 2;printf("%lld\n", ans);continue;}strcpy(s+1, t+1);reverse(t+1, t+1+len);s[0] = t[0] = '&';L.init(s, len); L.st();R.init(t, len); R.st();for (int i = 1; i <= len/2; ++i) { // 枚舉循環(huán)節(jié)int last = 1;for (int j = i+1; j <= len; j += i) { // 找到最長(zhǎng)的循環(huán)節(jié)為i的字符串if (L.lcp(last, j) >= i) continue;ans += work(last, j-1, i, len, k);if (j+i-1 <= len) last = j;else last = 0;}if (last) ans += work(last, len, i, len, k);}printf("%lld\n", ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU - 6661 Acesrc and String Theory (后缀数组)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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