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的理解。

/* ***************

Author        :kuangbin

Created Time  :2014/9/23 22:37:26

File Name     :E:\2014ACM\专题学习\后缀自动机\HDU4641.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 250010;

const int CHAR = 26;

struct SAM_Node{

	SAM_Node *fa,*next[CHAR];

	int len;

	int cnt;

	void clear(){

		fa = 0;

		memset(next,0,sizeof(next));

		cnt = 0;

	}

}pool[MAXN*2];

SAM_Node *root,*tail;

SAM_Node* newnode(int len){

	SAM_Node* cur = tail++;

	cur->clear();

	cur->len = len;

	return cur;

}

void SAM_init(){

	tail = pool;

	root = newnode(0);

}

SAM_Node* extend(SAM_Node* last,int x){

	SAM_Node *p = last, *np = newnode(p->len+1);

	while(p && !p->next[x])

		p->next[x] = np, p = p->fa;

	if(!p)np->fa = root;

	else{

		SAM_Node* q = p->next[x];

		if(q->len == p->len+1)np->fa = q;

		else {

			SAM_Node* nq = newnode(p->len+1);

			memcpy(nq->next,q->next,sizeof(q->next));

			nq->fa = q->fa;

			nq->cnt = q->cnt;

			q->fa = np->fa = nq;

			while(p && p->next[x] == q)

				p->next[x] = nq, p = p->fa;

		}

	}

	return np;

}

int K;

SAM_Node *last;

long long ans;

void calc(){

	SAM_Node *p = last;

	while(p && p->cnt < K){

		p->cnt++;

		if(p->cnt >= K){

			if(p->fa)

				ans += p->len - p->fa->len;

		}

		p = p->fa;

	}

}

char str[MAXN];

int main()

{

    int n,m;

	while(scanf("%d%d%d",&n,&m,&K) == 3){

		SAM_init();

		last = root;

		ans = 0;

		scanf("%s",str);

		int len = strlen(str);

		for(int i = 0;i < len;i++){

			last = extend(last,str[i]-'a');

			calc();

		}

		int op;

		while(m--){

			scanf("%d",&op);

			if(op == 2)printf("%I64d\n",ans);

			else {

				scanf("%s",str);

				last = extend(last,str[0]-'a');

				calc();

			}

		}

	}

    return 0;

}