HDU4641 || 6194多校 (后缀自动机-最少出现K次的字串个数 || 恰好出现K次字符串的个数)

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

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

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

 

分析：

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

#include<bits/stdc++.h>
using namespace std;
#define mem(a , b) memset(a , b , sizeof(a))
const int maxn = 250001;
#define ll long long

struct SAM{
    int trans[maxn<<1][26] , slink[maxn<<1] , maxlen[maxn<<1];
    int last , now , root;
    ll ans=0;
    int sum[maxn<<1];
    void newnode(int v)
    {
        maxlen[++now]=v;
        mem(trans[now],0);

    }
    void extend(int c , int k)
    {
        newnode(maxlen[last] + 1);
        int p = last , np = now;sum[now]=0;
     //  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] + 1 != maxlen[q])
            {
                newnode(maxlen[p] +1 );
                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 = 1;
        slink[root]=0;
        mem(trans[root],0);
        sum[root]=0;
        ans=0;
    }


}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=0 ; i<n ; i++)
    {
        sam.extend(str[i]-'a'  , k);
    }
    while(q--)
    {
        int T;scanf("%d",&T);
        getchar();
       
        if(T==1)
        { char op;
            op=getchar();
            sam.extend(op-'a' , k );
           // cout<<op<<endl;
        }
        else
        {
            printf("%lld\n",sam.ans);
        }
    }
    }

}

View Code

 

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

#include<bits/stdc++.h>
using namespace std;
#define mem(a , b) memset(a , b , sizeof(a))
const int maxn = 250001;
#define ll long long

struct SAM{
    int trans[maxn<<1][26] , slink[maxn<<1] , maxlen[maxn<<1];
    int last , now , root;
    ll ans=0;
    int sum[maxn<<1];
    void newnode(int v)
    {
        maxlen[++now]=v;
        mem(trans[now],0);

    }
    void extend(int c , int k)
    {
        newnode(maxlen[last] + 1);
        int p = last , np = now;sum[now]=0;
     //  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] + 1 != maxlen[q])
            {
                newnode(maxlen[p] +1 );
                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 = 1;
        slink[root]=0;
        mem(trans[root],0);
        sum[root]=0;
        ans=0;
    }


}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=0 ; i<n ; i++)
    {
        sam.extend(str[i]-'a'  , k);
    }
    ll sum1=sam.ans;
    sam.init();
    for(int i=0 ; i<n ; i++)
    {
        sam.extend(str[i]-'a'  , k+1);
    }
    ll sum2=sam.ans;
    printf("%lld\n",sum1-sum2);
    }

}

View Code

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄