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

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);

    }

}