題目鏈接
時間限制:15000ms
單點時限:3000ms
內存限制:512MB

描述

小Hi平時的一大興趣愛好就是演奏鋼琴。我們知道一個音樂旋律被表示為一段數構成的數列。

現在小Hi想知道一部作品中所有長度為K的旋律中出現次數最多的旋律的出現次數。但是K不是固定的，小Hi想知道對于所有的K的答案。

輸入

共一行，包含一個由小寫字母構成的字符串S。字符串長度不超過 1000000。

輸出

共Length(S)行，每行一個整數，表示答案。

樣例輸入

aab

樣例輸出

2
1
1

思路

后綴自動機板子
求相同長度字符串出現次數最多的字符串出現的次數

• 利用endpos的長度求解，每個endpos對應長度 minlen 到 maxlen的字符串，當我們知道所有的endpos之后，又因為ans[N]單調遞減，我們只需要維護maxlen對應的長度，從最后開始先前掃一遍更新max ans

#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 rep(i, a, n) for (int i = a; i <= n; ++i) const int maxn = 1e6+6; #define mid ((l + r) >> 1) #define lc rt<<1 #define rc rt<<1|1 using namespace std; // __int128 read() { __int128 x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f;} // void print(__int128 x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) print(x / 10); putchar(x % 10 + '0');} char s[maxn]; struct SAM{int trans[maxn<<1][26], slink[maxn<<1], maxlen[maxn<<1];// 用來求endposint indegree[maxn<<1], endpos[maxn<<1], rank[maxn<<1], ans[maxn<<1];int last, now, root, len;inline void newnode (int v) {maxlen[++now] = v;}inline void extend(int c) {newnode(maxlen[last] + 1);int p = last, np = now;// 更新transwhile (p && !trans[p][c]) {trans[p][c] = np;p = slink[p];}if (!p) slink[np] = root;else {int q = trans[p][c];if (maxlen[p] + 1 != maxlen[q]) {// 將q點拆出nq，使得maxlen[p] + 1 == maxlen[q]newnode(maxlen[p] + 1);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 build() {scanf("%s", s);len = strlen(s);root = last = now = 1;for (int i = 0; i < len; ++i) extend(s[i] - 'a');}// 拓撲排序inline void topsort() {for (int i = 1; i <= now; ++i) indegree[ maxlen[i] ]++; // 統計相同度數的節點的個數for (int i = 1; i <= now; ++i) indegree[i] += indegree[i-1]; // 統計度數小于等于 i 的節點的總數for (int i = 1; i <= now; ++i) rank[ indegree[ maxlen[i] ]-- ] = i; // 為每個節點編號，節點度數越大編號越靠后// 從下往上按照slik更新for (int i = now; i >= 1; --i) {int x = rank[i];endpos[slink[x]] += endpos[x];}}// 求不同的子串種類inline LL all () {LL ans = 0;for (int i = root+1; i <= now; ++i) {ans += maxlen[i] - maxlen[ slink[i] ];}return ans;}// 長度為K的字符串有多種，求出現次數最多的次數inline void get_maxk() {topsort();for (int i = 1; i <= now; ++i) {ans[maxlen[i]] = max(ans[maxlen[i]], endpos[i]);}for (int i = len; i >= 1; --i) ans[i] = max(ans[i], ans[i+1]);for (int i = 1; i <= len; ++i) //cout << ans[i] << endl; printf("%d\n", ans[i]);}}sam;int main() { #ifndef ONLINE_JUDGE// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout); #endifios::sync_with_stdio(false);cin.tie(0); cout.tie(0);sam.build();sam.get_maxk();return 0; }

總結

以上是生活随笔為你收集整理的hihoCoder #1449 : 后缀自动机三·重复旋律6的全部內容，希望文章能夠幫你解決所遇到的問題。

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