http://acm.hdu.edu.cn/showproblem.php?pid=4641

http://acm.hdu.edu.cn/showproblem.php?pid=6194

题意: 开始时给出一个字符串,给出两种操作,一种是在字符串后面添加一个字符,
另一个是查询出现过最少出现K次的字串个数。

分析:

建立后缀自动机,添加一个字符插入即可,对于查询,前面计算过的没必要再算,
直接从当前开始往前面找,已经达到K次的就不管,说明前面已经计算过,现在达到
K次的加进答案。

#include<bits/stdc++.h>
using namespace std;
#define mem(a , b) memset(a , b , sizeof(a))
const int maxn = ;
#define ll long long struct SAM{
int trans[maxn<<][] , slink[maxn<<] , maxlen[maxn<<];
int last , now , root;
ll ans=;
int sum[maxn<<];
void newnode(int v)
{
maxlen[++now]=v;
mem(trans[now],); }
void extend(int c , int k)
{
newnode(maxlen[last] + );
int p = last , np = now;sum[now]=;
// cout<<now<<endl;
while(p && !trans[p][c])
{
trans[p][c] = np;
p = slink[p];
}
if(!p) slink[np] = root;
else
{
int q = trans[p][c];
if(maxlen[p] + != maxlen[q])
{
newnode(maxlen[p] + );
int nq = now;
memcpy(trans[nq] , trans[q] , sizeof(trans[q]));
sum[nq]=sum[q];///分开的节点要继承
slink[nq] = slink[q];
slink[q] = slink[np] = nq;
while(p && trans[p][c] == q)
{
trans[p][c] = nq;
p = slink[p];
}
}
else
{
slink[np]=q;
}
}
last = np;
int w=np;
while(w && sum[w] < k )
{
sum[w]++;
if(sum[w]==k) ans+=maxlen[w]-maxlen[slink[w]];
w=slink[w];
}
// cout<<np<<endl;
}
void init()
{
root = last = now = ;
slink[root]=;
mem(trans[root],);
sum[root]=;
ans=;
} }sam;
int main()
{ int n,q,k;
while(scanf("%d%d%d",&n,&q,&k)!=EOF){
sam.init();
char str[maxn];scanf("%s",str);
for(int i= ; i<n ; i++)
{
sam.extend(str[i]-'a' , k);
}
while(q--)
{
int T;scanf("%d",&T);
getchar(); if(T==)
{ char op;
op=getchar();
sam.extend(op-'a' , k );
// cout<<op<<endl;
}
else
{
printf("%lld\n",sam.ans);
}
}
} }

关于恰好出现k次的字符串 , 我们只要求出至少k次的字串 - 至少(k+1)次的字串 ,不恰好就是k次吗

#include<bits/stdc++.h>
using namespace std;
#define mem(a , b) memset(a , b , sizeof(a))
const int maxn = ;
#define ll long long struct SAM{
int trans[maxn<<][] , slink[maxn<<] , maxlen[maxn<<];
int last , now , root;
ll ans=;
int sum[maxn<<];
void newnode(int v)
{
maxlen[++now]=v;
mem(trans[now],); }
void extend(int c , int k)
{
newnode(maxlen[last] + );
int p = last , np = now;sum[now]=;
// cout<<now<<endl;
while(p && !trans[p][c])
{
trans[p][c] = np;
p = slink[p];
}
if(!p) slink[np] = root;
else
{
int q = trans[p][c];
if(maxlen[p] + != maxlen[q])
{
newnode(maxlen[p] + );
int nq = now;
memcpy(trans[nq] , trans[q] , sizeof(trans[q]));
sum[nq]=sum[q];///分开的节点要继承
slink[nq] = slink[q];
slink[q] = slink[np] = nq;
while(p && trans[p][c] == q)
{
trans[p][c] = nq;
p = slink[p];
}
}
else
{
slink[np]=q;
}
}
last = np;
int w=np;
while(w && sum[w] < k )
{
sum[w]++;
if(sum[w]==k) ans+=maxlen[w]-maxlen[slink[w]];
w=slink[w];
}
// cout<<np<<endl;
}
void init()
{
root = last = now = ;
slink[root]=;
mem(trans[root],);
sum[root]=;
ans=;
} }sam;
int main()
{ int n,q,k;
int t;scanf("%d",&t);
while(t--)
{ string str;int k;
cin>>k>>str;
sam.init();
n=str.size();
for(int i= ; i<n ; i++)
{
sam.extend(str[i]-'a' , k);
}
ll sum1=sam.ans;
sam.init();
for(int i= ; i<n ; i++)
{
sam.extend(str[i]-'a' , k+);
}
ll sum2=sam.ans;
printf("%lld\n",sum1-sum2);
} }
05-08 15:30