链接：http://acm.hdu.edu.cn/showproblem.php?pid=4641
题意：有一个长度为n(n < 5e4)的字符串，Q（Q<=2e5）次操作；操作分为：在末尾插入一个字符ch和查询不同子串出现次数不小于K的数量；
思路1:SAM在线求解；
对于每次找到将一个字符x插入到SAM之后，我们知道pre[p]所含有的Tx的后缀字符串数目为step[pre[np]]个，那么只需要每次插入之后更新下这些字符串出现的次数cnt即可；
由于Right(fa)与Right(r)没有交集（max(fa) = min(r) - 1）,所以需要一直递推到root，但是root不能计算，因为root并没有表示后缀，只是一个init状态；
还有一点就是在拷贝q的信息到nq中时，主要把cnt的信息也拷贝过去；
由于数据较弱。。当出现5e4长度均为a的字符串，2e5次插入操作；这个算法复杂度将达到O(T*n*Q)；
（因为每插入一个字符，都需要更新5e4次父节点，这时上面的flag优化没什么卵用。。）
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; #define maxn 100007
#define SIGMA_SIZE 26 struct SAM{
int sz,tot,last,k;
int g[maxn<<][SIGMA_SIZE],pre[maxn<<],step[maxn<<];
int vs[maxn<<],cnt[maxn<<]; void newNode(int s){
step[++sz] = s;
pre[sz] = ;
vs[sz] = cnt[sz] = ;
memset(g[sz],,sizeof(g[sz]));
} void init(){
tot = ;
sz = ; last = ;
newNode();
} int idx(char ch){return ch - 'a';} void Insert(char ch){
newNode(step[last]+);
int v = idx(ch), p = last, np = sz; while(p && !g[p][v])
g[p][v] = np,p = pre[p]; //知道找到Right集合中包含x的边的祖宗节点 if(p){
int q = g[p][v];
if(step[q] == step[p] + )
pre[np] = q;
else{
newNode(step[p]+);
int nq = sz; //nq替换掉q节点
for(int i = ;i < SIGMA_SIZE;i++)
g[nq][i] = g[q][i]; cnt[nq] = cnt[q]; //**
pre[nq] = pre[q];
pre[np] = pre[q] = nq; while(p && g[p][v] == q)
g[p][v] = nq,p = pre[p];
}
}
else pre[np] = ;
for(int aux = np;aux != && !vs[aux];aux = pre[aux]){
if(++cnt[aux] >= k){
tot += step[aux] - step[pre[aux]];
vs[aux] = true; //该父节点的子串已经加到tot中
}
}
last = np;
}
}SA;
char str[maxn];
int main()
{
int n,Q;
while(scanf("%d%d%d",&n,&Q,&SA.k) == ){
scanf("%s",str);
SA.init();
int len = strlen(str);
for(int i = ;i < len;i++){
SA.Insert(str[i]);
}
int op;
char ch[];
while(Q--){
scanf("%d",&op);
if(op & ){
scanf("%s",ch);
SA.Insert(ch[]);
}
else printf("%d\n",SA.tot);
}
}
}
思路2：SAM离线+并查集优化
将操作全部插入到SAM并存储之后，先进行拓扑排序；
1.为什么要进行拓扑排序？
因为拓扑的目的是为了使得SAM分层，即之后可以使用后缀数组基数排序的思想得到每个节点状态的|Right|即包含的子节点个数；
思路1由于是在线算法，并不需要知道一个节点的所有子节点（在线+1）；
2.并查集优化哪里？ <=> 如何逆向删除末尾加入的字符？
删除字符其实就是在Insert时存储下来每个字符对应的节点id，之后用并查集Find(p)来得到每次删除时，实际上该节点已经转移到哪个祖先节点的思想；
并且删除有两次，一次是开始就小于K次，就一次删到大于K次，这时该节点由于一条路径被删了，更改之后看是否也小于K次，循环即可；
时间复杂度为O(T*(n+m))
代码参考：JeraKrs
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; #define maxn 250007
#define SIGMA_SIZE 26
int ans[maxn],op[maxn];
char str[maxn];
int N,Q,K; struct SAM{
int sz,last;
int g[maxn<<][SIGMA_SIZE], pre[maxn<<], step[maxn<<];
int cnt[maxn<<], pos[maxn<<], id[maxn<<];
int f[maxn<<], sub[maxn<<]; int Find(int x){ return f[x] == x? x: f[x] = Find(f[x]); } void init(){
sz = ;last = ;
newNode();
} void newNode(int s){
pre[++sz] = ;
step[sz] = s;
memset(g[sz],,sizeof(g[sz]));
} int idx(char ch){ return ch - 'a'; } void Insert(char ch);
void topoSort();
void getCnt();
void solve(int Q,int *op,int K); }SA; void SAM::Insert(char ch){
newNode(step[last] + );
int v = idx(ch), np = sz, p = last;
id[N] = np;
while(p && !g[p][v]){
g[p][v] = np;
p = pre[p];
} if(p){
int q = g[p][v];
if(step[q] == step[p] + )
pre[np] = q;
else{
newNode(step[p] + );
int nq = sz;
for(int i = ;i < SIGMA_SIZE;i++)
g[nq][i] = g[q][i]; pre[nq] = pre[q];
pre[q] = pre[np] = nq; while(p && g[p][v] == q)
g[p][v] = nq, p = pre[p];
}
}
else pre[np] = ;
last = np;
} void SAM::topoSort(){
for(int i = ; i <= sz; i++) cnt[i] = ;
for(int i = ; i <= sz; i++) cnt[step[i]]++;
for(int i = ; i <= sz; i++) cnt[i] += cnt[i-];
for(int i = ; i <= sz; i++) pos[cnt[step[i]]--] = i;
} void SAM::getCnt(){
for(int i = ; i <= sz; i++) cnt[i] = ;
for(int p = ,i = ; i < N;i++){
int v = idx(str[i]);
p = g[p][v];
cnt[p] = ; //必须是后缀才能赋值root为0
} for(int i = sz; i; i--){
int p = pos[i];
cnt[pre[p]] += cnt[p];
}
} void SAM::solve(int Q,int *op,int K){
long long ret = ;
for(int i = ; i <= sz;i++){
int p = pos[i];
if(cnt[p] >= K) ret += step[p] - step[pre[p]];
} for(int i = ;i <= sz;i++) f[i] = i, sub[i] = ; for(int i = Q; i; i--){
if(op[i] == ) ans[i] = ret;
else{
int p = id[N--];
int fp = Find(p);
while(fp && cnt[fp] < K){
p = f[fp] = pre[fp]; //更新
fp = Find(p); //压缩
}
if(fp == ) continue;
sub[fp]++;
while(fp && cnt[fp] - sub[fp] < K){ //由于单调性 cnt[fp] >= K 是一定成立的
ret -= step[fp] - step[pre[fp]];
p = f[fp] = pre[fp];
sub[pre[fp]] += sub[fp];
fp = Find(p);
}
}
} } int main()
{
while(scanf("%d%d%d",&N,&Q,&K) == ){
scanf("%s",str);
SA.init();
for(int i = ; i < N; i++)
SA.Insert(str[i]);
char aux[];
for(int i = ;i <= Q; i++){
scanf("%d",op + i);
if(op[i] & ){
scanf("%s",aux);
str[N++] = aux[];
SA.Insert(aux[]);
}
}
str[N] = '\0';
SA.topoSort();
SA.getCnt();
SA.solve(Q,op,K); for(int i = ;i <= Q;i++)
if(op[i] == ) printf("%d\n",ans[i]);
}
}