HDU 4641 K-string （SAM）

HDU 4641 K-string （SAM）

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 2abc21 a21 a2

Sample Output

011

题意

对于一个长度为 n

向字符串的末尾增加一个字符 c

查询串中至少出现 m

思路

我们用原串建立后缀自动机，显然第一种操作即一次 ​​insert​​ 。

对于第二种操作，我们考虑每一次的 ​​insert​​ ，对新加入节点 u−>S 的状态路径 num[np]+1 ，若此时的 num[np]>=m 则说明当前状态下所有子串的出现次数都已达到 m ，因此 ans+=step[np]−step[pre[np]]

最终的 ans

AC 代码

#include using namespace std;typedef long long LL;const int maxn = 5e5+10;LL ans, K;struct SAM{ int ch[maxn][26]; int pre[maxn], step[maxn]; int last, id; int num[maxn]; void init() { last = id = 0; memset(ch[0], -1, sizeof(ch[0])); pre[0] = -1; step[0] = 0; } void insert(int c) { int p = last, np = ++id; step[np] = step[p] + 1; memset(ch[np], -1, sizeof(ch[np])); num[np] = 0; while (p != -1 && ch[p][c] == -1) ch[p][c] = np, p = pre[p]; if (p == -1) pre[np] = 0; else { int q = ch[p][c]; if (step[q] != step[p] + 1) { int nq = ++id; memcpy(ch[nq], ch[q], sizeof(ch[q])); num[nq] = num[q]; step[nq] = step[p] + 1; pre[nq] = pre[q]; pre[np] = pre[q] = nq; while (p != -1 && ch[p][c] == q) ch[p][c] = nq, p = pre[p]; } else pre[np] = q; } last = np; /* diy */ while (np != -1 && num[np] < K) { num[np]++; if (num[np] >= K) ans += step[np] - step[pre[np]]; np = pre[np]; } /* end diy */ }} sam;char str[maxn];int main(){ int n, q; while (~scanf("%d%d%I64d%*c", &n, &q, &K)) { sam.init(); ans = 0; gets(str); for (int i = 0; i < n; i++) sam.insert(str[i] - 'a'); for (int i = 0; i < q; i++) { int op; scanf("%d%*c", &op); if (op == 1) { char c; c = getchar(); sam.insert(c - 'a'); } else printf("%I64d\n", ans); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。