首页 > 代码库 > HDU4641_K-string

HDU4641_K-string

2024-07-09 09:44:29   211人阅读

若它的一个子串出现的次数不少于K次，那么这个子串就是一个K-string。

现给出原串，每次可以向该串后面添加一个字符或者询问当前有多少个不同的K-string。

在线添加查询，解法直指SAM。

其实给添加函数直接设置一个返回值直接更新ans就好了。

对于每个状态，多开一个值记录它的出现次数，每次添加点过后，沿着last点的pre指正一边走一边判断就好了。

注意，每个点不要重复计算，如果一个点计算前就已经被标记计算了，那么pre上的其他的点也不需要计算了，显然。

 

召唤代码君：

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 1000500using namespace std;int next[maxn][26],pre[maxn],step[maxn],g[maxn];int N,last,n,m,k;long long ans;int p,q,np,nq;char s[maxn];bool vis[maxn];int add(){	N++;	pre[N]=step[N]=g[N]=0;	vis[N]=false;	for (int i=0; i<26; i++) next[N][i]=0;	return N;}void insert(int x){	p=last;np=add();step[np]=step[last]+1;last=np;	while (p!=-1 && next[p][x]==0) next[p][x]=np,p=pre[p];	if (p==-1) return;	q=next[p][x];	if (step[q]==step[p]+1) { pre[np]=q; return; }	nq=add();step[nq]=step[p]+1;pre[nq]=pre[q];g[nq]=g[q];vis[nq]=vis[q];	for (int i=0; i<26; i++) next[nq][i]=next[q][i];	pre[np]=pre[q]=nq;	while (p!=-1 && next[p][x]==q) next[p][x]=nq,p=pre[p];}void count(){	for (p=last; p!=0 && !vis[p]; p=pre[p]) 	{		g[p]++;		if (g[p]>=k) 		{			ans+=step[p]-step[pre[p]];			vis[p]=true;		}	}}int main(){	while (scanf("%d%d%d",&n,&m,&k)!=EOF)	{		N=-1;N=add();pre[0]=-1;last=0;ans=0;		scanf("%s",s);		for (int i=0; s[i]; i++) insert(s[i]-‘a‘),count();		while (m--) 		{			scanf("%d",&n);			if (n==2) printf("%I64d\n",ans);				else { scanf("%s",s); insert(s[0]-‘a‘); count(); }		}	}	return 0;}

　　

 


联系
我们