牛客-139 I. Substring(后綴數組 or 后綴自動機)

題目鏈接

題意

一個由$\{a,b,c\}$組成的字符串$S$,求S子串的最大的集合,使得集合里的字符串互不同構

思路一:后綴數組

一共有3種字符,所以一共有6中映射關系,首先將字符串轉化為6個同構的字符串.

然后求這個字符串一共有多少個不同的字符串

非連續的子串"$aab$",與他同構的有6種并且6種字符串都不相同

連續的子串"aaa",與他同構的有3種

所以連續的子串少算3個,求出不同字符串之后加上少算的字符串剛好是答案的6倍

#include <bits/stdc++.h> const int maxn = 3e5 + 10; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; char s[maxn], ss[maxn], t[4] = "ABC";struct SuffixArray{ // 下標1int cntA[maxn], cntB[maxn], A[maxn], B[maxn];int n, Sa[maxn], tSa[maxn], height[maxn], Rank[maxn]; // Sa[i] 排名第i的下標， Rank[i] 下標i的排名void init(char *buf, int len) { // 下標1，sa，rank，heightn = len;for (int i = 0; i < 500; ++i) cntA[i] = 0;for (int i = 1; i <= n; ++i) cntA[(int)buf[i]]++;for (int i = 1; i < 500; ++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;}} }S; int main() {int n;while (scanf("%d%s", &n, s) != EOF) {int now = 0;char c = 'Z';map<char, char> mp;do{mp['a'] = t[0];mp['b'] = t[1];mp['c'] = t[2];for (int i = 0; i < n; ++i) {ss[++now] = mp[s[i]];}ss[++now] = ++c;}while (next_permutation(t, t+3));S.init(ss, now);long long ans = 1ll * (n+1) * n * 3;for (int i = 1; i <= n*6; ++i) {ans -= S.height[i];}int tmp = 1, cnt = 1;for (int i = 1; i < n; ++i) {if (s[i] == s[i-1]) tmp++;else tmp = 1;cnt = max(cnt, tmp);}ans += cnt * 3;printf("%lld\n", ans/6);}return 0; }

思路二:廣義后綴自動機

對6個串建廣義自動機,然后類似思路一求不同子串的個數,加上少算的除以6即可

#include <bits/stdc++.h> const int maxn = 3e5 + 5; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; struct SAM{int trans[maxn<<1][3], slink[maxn<<1], maxlen[maxn<<1];// 用來求endposint indegree[maxn<<1], endpos[maxn<<1], rank[maxn<<1], ans[maxn<<1];// 計算所有子串的和(0-9表示)long sum[maxn<<1];int last, now, root, len;inline void newnode (int v) {maxlen[++now] = v;}inline void init() {root = now = 1;memset(trans, 0, sizeof(trans));// memset(slink, 0, sizeof(slink));// memset(maxlen, 0, sizeof(maxlen));}inline void extend(int c) {if (trans[last][c]) { // 廣義自動機 節點合并 節省空間int p = last, np = trans[last][c];if (maxlen[last] + 1 == maxlen[np]) last = np;else {int q = trans[p][c];newnode(maxlen[p]+1);int nq = now;memcpy(trans[nq], trans[q], sizeof(trans[q]));slink[nq] = slink[q];slink[q] = last = nq;while (p && trans[p][c] == q) {trans[p][c] = nq;p = slink[p];}}return;}newnode(maxlen[last] + 1); // 新建節點int p = last, np = now;// 更新transwhile (p && !trans[p][c]) { // last的slink只想新節點trans[p][c] = np;p = slink[p];}if (!p) slink[np] = root; else { // slink中存在節點有到c的邊int q = trans[p][c];if (maxlen[p] + 1 != maxlen[q]) { // 判斷是否為同一個endposnewnode(maxlen[p] + 1); // 將q點拆出nq，使得maxlen[p] + 1 == maxlen[q]int nq = now;memcpy(trans[nq], trans[q], sizeof(trans[q]));slink[nq] = slink[q];slink[q] = slink[np] = nq;while (p && trans[p][c] == q) {trans[p][c] = nq;p = slink[p];} }else slink[np] = q;}last = np;// 初始狀態為可接受狀態endpos[np] = 1;}inline void insert(char *buf) {len = strlen(buf);last = 1;for (int i = 0; i < len; ++i) extend(buf[i] - '0'); // extend(s[i] - '1');}// 求不同的子串種類inline long long all () {long long ans = 0;for (int i = root+1; i <= now; ++i) {ans += maxlen[i] - maxlen[ slink[i] ];}return ans;} }sam; char s[maxn], ss[maxn], t[4] = "012"; int main() {int n;while (scanf("%d%s", &n, s) != EOF) {sam.init();do{for (int i = 0; i < n; ++i) {ss[i] = t[s[i]-'a'];}sam.insert(ss);}while(next_permutation(t, t+3));long long ans = sam.all();int tmp = 1, sum = 1;for (int i = 1; i < n; ++i) {if (s[i] == s[i-1]) ++tmp;else tmp = 1;sum = max(sum, tmp);}ans += sum * 3;printf("%lld\n", ans/6);}return 0; }

總結

以上是生活随笔為你收集整理的牛客-139 I. Substring(后缀数组 or 后缀自动机)的全部內容，希望文章能夠幫你解決所遇到的問題。

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