首页 > > 程序设计 > C/C++ >

hihoCoder_1445_后缀自动机二·重复旋律…

2018-06-17 21:47:55来源：未知阅读 ()

#1445 : 后缀自动机二·重复旋律5

时间限制:10000ms

单点时限:2000ms

内存限制:512MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。

现在小Hi想知道一部作品中出现了多少不同的旋律？

解题方法提示

输入

共一行，包含一个由小写字母构成的字符串。字符串长度不超过 1000000。

输出

一行一个整数，表示答案。

样例输入

aab

样例输出

　　　　5

后缀自动机中节点表示的后缀是连续的几个后缀
这里连续的意味着以相同节点结尾的几个后缀的长度是连续的比如长度分别是3和4和5
而当前节点的最短后缀长度是par指向节点的len+1
因此当前节点所代表所有后缀的个数是以当前节点结尾的后缀的最大长度减最小长度加一
而一般后缀自动机中对于当前节点的minlen是不用存储的，只要访问par节点的len即可，而后缀自动机中的len一般指maxlen，par和link都是同样一个意思

 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 SAM{
25     int n, root, last, tot;
26     struct node{
27         int len;
28         int link, go[26];
29     };
30     node state[maxn<<1];
31     void init(char *str){
32         n=strlen(str);
33         tot=1;
34         root=1;
35         last=1;
36         memset(&state,0,sizeof(state));
37     }
38     void extend(int w){
39         tot++;
40         int p=last;
41         int np=tot;
42         state[np].len=state[p].len+1;
43         while(p && state[p].go[w]==0){
44             state[p].go[w]=np;
45             p=state[p].link;
46         }
47         if(p==0){
48             state[np].link=root;
49         }else{
50             int q=state[p].go[w];
51             if(state[p].len+1==state[q].len){
52                 state[np].link=q;
53             }else{
54                 tot++;
55                 int nq=tot;
56                 state[nq].len=state[p].len+1;
57                 memcpy(state[nq].go,state[q].go,sizeof(state[q].go));
58                 state[nq].link=state[q].link;
59                 state[q].link=nq;
60                 state[np].link=nq;
61                 while(p && state[p].go[w]==q){
62                     state[p].go[w]=nq;
63                     p=state[p].link;
64                 }
65             }
66         }
67         last=np;
68     }
69     void build(char *str){
70         init(str);
71         for(int i=0;i<n;i++)
72             extend(str[i]-'a');
73     }
74     LL substring_num(void){
75         LL ans=0LL;
76         for(int i=root;i<=tot;i++)
77             ans+=state[i].len-state[state[i].link].len;
78         return ans;
79     }
80 };
81 SAM A;
82 char str[maxn];
83 int main(){
84     // freopen("in.txt","r",stdin);
85     // freopen("out.txt","w",stdout);
86     while(~scanf("%s",str)){
87         A.build(str);
88         printf("%lld\n",A.substring_num());
89     }
90     return 0;
91 }