hihoCoder_1449_后缀自动机三·重复旋律…
2018-06-17 21:48:46来源:未知 阅读 ()
#1449 : 后缀自动机三·重复旋律6
描述
小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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:线段树题解(3题)
- HihoCoder 1174 2020-02-15
- 【题解】洛谷 P1449 后缀表达式 2019-10-08
- 中缀表达式转后缀表达式 2019-04-30
- LOJ#111. 后缀排序(二分 hash) 2018-08-02
- POJ1743 Musical Theme(后缀数组 二分) 2018-07-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash