HDU4641 因为需要一个在线的算法！ 明显可以用后缀自动机搞。 每个一个字符，就统计下每个点出现的次数，从而更新答案。 后面自动机沿着 fa 指针往前跳，可以找到所有后缀，累加值。
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 102400/131072 K (Java/Others) Total Submission(s): 535 Accepted Submission(s): 175
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.
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).
For each query print an integer — the number of different K-string currently.
3 5 2 abc 2 1 a 2 1 a 2
0 1 1