HDU 4641 K-string

K-string

Time Limit: 2000ms

Memory Limit: 131072KB

This problem will be judged on HDU. Original ID: 4641
64-bit integer IO format: %I64d Java class name: Main

Given a string S. K-string is the sub-string of S and it appear in the S at least K times.It means there are at least K different pairs (i,j) so that Si,Si+1... Sj equal to this K-string. Given m operator or query:1.add a letter to the end of S; 2.query how many different K-string currently.For each query ,count the number of different K-string currently.

Input

The input consists of multiple test cases.
Each test case begins with a line containing three integers n, m and K(1<=n,K<=50000,1<=m<=200000), denoting the length of string S, the number of operator or question and the least number of occurrences of K-string in the S.
The second line consists string S,which only contains lowercase letters.
The next m lines describe the operator or query.The description of the operator looks as two space-separated integers t c (t = 1; c is lowercase letter).The description of the query looks as one integer t (t = 2).

Output

For each query print an integer — the number of different K-string currently.

Sample Input

3 5 2
abc
2
1 a
2
1 a
2

Sample Output

0
1
1

Source

2013 Multi-University Training Contest 4

解题：后缀自动机

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 600010;
 5 int n,m,k;
 6 LL ret;
 7 struct node{
 8     int son[26],f,len,num;
 9     void init(){
10         f = -1;
11         num = len = 0;
12         memset(son,-1,sizeof son);
13     }
14 };
15 struct SAM{
16     node e[maxn];
17     int tot,last;
18     int newnode(int len = 0){
19         e[tot].init();
20         e[tot].len = len;
21         return tot++;
22     }
23     void init(){
24         tot = last = 0;
25         newnode();
26     }
27     void add(int c){
28         int p = last,np = newnode(e[p].len + 1);
29         while(p != -1 && e[p].son[c] == -1){
30             e[p].son[c] = np;
31             p = e[p].f;
32         }
33         if(p == -1) e[np].f = 0;
34         else{
35             int q = e[p].son[c];
36             if(e[p].len + 1 == e[q].len) e[np].f = q;
37             else{
38                 int nq = newnode();
39                 e[nq] = e[q];
40                 e[nq].len = e[p].len + 1;
41                 e[q].f = e[np].f = nq;
42                 while(p != -1 && e[p].son[c] == q){
43                     e[p].son[c] = nq;
44                     p = e[p].f;
45                 }
46             }
47         }
48         for(p = np; p != -1; p = e[p].f){
49             if(e[p].num == k) break;
50             if(++e[p].num == k){
51                 ret += e[p].len - e[e[p].f].len;
52                 break;
53             }
54         }
55         last = np;
56     }
57 }sam;
58 char str[maxn];
59 int main(){
60     int op;
61     while(~scanf("%d%d%d",&n,&m,&k)){
62         scanf("%s",str);
63         sam.init();
64         ret = 0;
65         for(int i = 0; str[i]; ++i)
66             sam.add(str[i] - 'a');
67         for(int i = 0; i < m; ++i){
68             scanf("%d",&op);
69             if(op == 1){
70                 scanf("%s",str);
71                 sam.add(str[0] - 'a');
72             }else printf("%d
",ret);
73         }
74     }
75     return 0;
76 }

View Code