#1449 : 尾碼自動機三·重覆旋律6 #1449 : 尾碼自動機三·重覆旋律6 時間限制:15000ms 單點時限:3000ms 記憶體限制:512MB 描述 小Hi平時的一大興趣愛好就是演奏鋼琴。我們知道一個音樂旋律被表示為一段數構成的數列。 現在小Hi想知道一部作品中所有長度為K的旋律中出現次 ...
#1449 : 尾碼自動機三·重覆旋律6
時間限制:15000ms 單點時限:3000ms 記憶體限制:512MB描述
小Hi平時的一大興趣愛好就是演奏鋼琴。我們知道一個音樂旋律被表示為一段數構成的數列。
現在小Hi想知道一部作品中所有長度為K的旋律中出現次數最多的旋律的出現次數。但是K不是固定的，小Hi想知道對於所有的K的答案。
輸入
共一行，包含一個由小寫字母構成的字元串S。字元串長度不超過 1000000。
輸出
共Length(S)行，每行一個整數，表示答案。
- 樣例輸入
-
aab - 樣例輸出
-
2 1 1
- 要求長度為k的子串中出現次數最多的串的出現次數
- 對於每個節點代表的子串出現次數的求法是拓撲排序之後從len最大的逐步向前更新之前節點的出現次數
- 原理是沿著par指針向前訪問節點意味著訪問的是同一最大子串的連續的子串
- 比如長度最大的串是abcdef是len最大的節點表示的最長串，最短串是abcd，那麼沿par指針訪問前一個節點，那麼前一個節點表示的子串是ab到abc，所以最長串出現多少次，沿par訪問的串就會出現多少次
- 在實際操作過程中對於extend操作中第一個新建的節點，打標記，意思當前串出現1次，而extend操作中衍生出的nq節點就標記為0
- 自動機完成後就是對於自動機拓撲排序，用len長的更新len短的得到每一個節點代表子串出現次數，用ans[length]記錄每個長度的最大出現次數
- 但是要註意此時的ans數組不是最後答案，因為ans數組還要滿足一個基本條件，即段子串出現次數一定比長子串出現次數多，就是說ans數組應該是一個非嚴格遞減序列
- 我們倒著遍歷ans數組，ans[i]=max(ans[i],ans[i+1]);
- 原因也好總結，因為尾碼數組記錄的len是匹配最大長度，我們沒有記錄minlen，所以對於一個節點出現次數我們沒有更新對應的minlen對應長度的出現次數，就是說在不同自動機路徑中我們沒法保證把1到n長度子串出現次數全部一次性統計正確，因為會有路徑上將很多長度的子串次數集中記錄在最大的長度len上而沒有對於小長度進行更新
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <climits> 7 #include <cmath> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL ; 15 typedef unsigned long long ULL ; 16 const int maxn = 1e6 + 10 ; 17 const int inf = 0x3f3f3f3f ; 18 const int npos = -1 ; 19 const int mod = 1e9 + 7 ; 20 const int mxx = 100 + 5 ; 21 const double eps = 1e-6 ; 22 const double PI = acos(-1.0) ; 23 24 struct cnode{ 25 int len, st; 26 cnode(int x, int y){ 27 len=x; st=y; 28 } 29 }; 30 bool ccmp(const cnode l, const cnode r){ 31 return l.len>r.len; 32 } 33 struct SAM{ 34 int n, tot, root, last; 35 int cnt[maxn<<1], ans[maxn]; 36 struct node{ 37 int len, flag; 38 int link, go[26]; 39 }; 40 node state[maxn<<1]; 41 void init(char *str){ 42 n=strlen(str); 43 tot=1; 44 root=1; 45 last=1; 46 memset(&state,0,sizeof(state)); 47 } 48 void extend(int w){ 49 tot++; 50 int p=last; 51 int np=tot; 52 state[np].len=state[p].len+1; 53 state[np].flag=1; 54 while(p && state[p].go[w]==0){ 55 state[p].go[w]=np; 56 p=state[p].link; 57 } 58 if(p==0){ 59 state[np].link=root; 60 }else{ 61 int q=state[p].go[w]; 62 if(state[p].len+1==state[q].len){ 63 state[np].link=q; 64 }else{ 65 tot++; 66 int nq=tot; 67 state[nq].len=state[p].len+1; 68 state[nq].flag=0; 69 memcpy(state[nq].go,state[q].go,sizeof(state[q].go)); 70 state[nq].link=state[q].link; 71 state[q].link=nq; 72 state[np].link=nq; 73 while(p && state[p].go[w]==q){ 74 state[p].go[w]=nq; 75 p=state[p].link; 76 } 77 } 78 } 79 last=np; 80 } 81 void build(char *str){ 82 init(str); 83 for(int i=0;i<n;i++) 84 extend(str[i]-'a'); 85 } 86 std::vector<cnode> v; 87 void solve(void){ 88 v.clear(); 89 for(int i=1;i<=tot;i++){ 90 cnt[i]=state[i].flag; 91 v.push_back(cnode(state[i].len,i)); 92 } 93 sort(v.begin(),v.end(),ccmp); 94 for(int i=0;i<v.size();i++){ 95 cnt[state[v[i].st].link]+=cnt[v[i].st]; 96 } 97 memset(ans,0,sizeof(ans)); 98 for(int i=1;i<=tot;i++) 99 ans[state[i].len]=max(ans[state[i].len],cnt[i]); 100 for(int i=n-1;i>0;i--) 101 ans[i]=max(ans[i],ans[i+1]); 102 for(int i=1;i<=n;i++) 103 printf("%d\n",ans[i]); 104 } 105 }; 106 SAM A; 107 char str[maxn]; 108 int main(){ 109 // freopen("in.txt","r",stdin); 110 // freopen("out.txt","w",stdout); 111 while(~scanf("%s",str)){ 112 A.build(str); 113 A.solve(); 114 } 115 return 0; 116 }
