#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("%dn",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 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
