HDU4641 因为需要一个在线的算法！ 明显可以用后缀自动机搞。 每个一个字符，就统计下每个点出现的次数，从而更新答案。 后面自动机沿着 fa 指针往前跳，可以找到所有后缀，累加值。

# K-string

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 102400/131072 K (Java/Others) Total Submission(s): 535 Accepted Submission(s): 175

Problem Description

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

写起来还是很简单的，主要是要加深对SAM的理解。

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 406.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%