Count the string kmp

时间：2022-03-13 09:26:16

　　

问题描述
众所周知，aekdycoin擅长字符串问题和数论问题。当给定一个字符串s时，我们可以写下该字符串的所有非空前缀。例如：
S：“ABAB”
前缀是：“A”、“AB”、“ABA”、“ABAB”
对于每个前缀，我们可以计算它在s中匹配的次数，因此我们可以看到前缀“a”匹配两次，“ab”也匹配两次，“ab a”匹配一次，“ab ab”匹配一次。现在，您需要计算所有前缀的匹配时间之和。对于“abab”，它是2+2+1+1=6。
答案可能非常大，因此输出答案mod 10007。

输入
第一行是一个整数t，表示测试用例的数量。对于每种情况，第一行是一个整数n（1<=n<=200000），它是字符串s的长度。后面的一行给出字符串s。字符串中的字符都是小写字母。

产量
对于每种情况，只输出一个数字：s mod 10007所有前缀的匹配时间总和。

对s进行lens次的分割  然后不断kmp  但是超时了

#include<bits/stdc++.h>

using namespace std;

//input

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define repp(i,a,b) for(int i=(a);i>=(b);i--)

#define RI(n) scanf("%d",&(n))

#define RII(n,m) scanf("%d%d",&n,&m);

#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)

#define RS(s) scanf("%s",s);

#define ll long long

#define inf 0x3f3f3f3f

#define REP(i,N)  for(int i=0;i<(N);i++)

#define CLR(A,v)  memset(A,v,sizeof A)

//////////////////////////////////

#define N 200000+5

#define mod 10007

string s,p;

int ans;

int lens,lenp;

int nex[N];

void getnext()

{

    nex[]=-;

    int k=-,j=;

    while(j<lenp-)

    {

        if(k==-||p[j]==p[k])

            nex[++j]=++k;

        else k=nex[k];

    }

}

int kmp()

{

    int j=,i=;

    while(i<lens&&j<lenp)

    {

        if(s[i]==p[j]||j==-)

        {

            i++;

            j++;

        }

        else j=nex[j];

        if(j==lenp)

        {

            ans++;j=;

        }

    }

}

int main()

{

    int cas;

    RI(cas);

    while(cas--)

    {

        RI(lens);

        ans=;

        cin>>s;

        for(lenp=;lenp<=lens;lenp++)

        {

            p=s.substr(,lenp);

            getnext();

            kmp();

        }

         cout<<ans<<endl;

    }

    return ;

}

显然都200000了  必然会超时的

这题其实用不到kmp  主要是next数组

next数组才是kmp的精髓 ！！！！！！

对p进行next扫描

初始化:cnt=lenp

如果next为0肯定没有可匹配的

如果next不为0 肯定有至少一个相匹配的

如果前后缀没有交集  肯定是一个匹配的

如果有交集  为1+交集中 相匹配的（ 因为交集中的字符串  就是最后的字符串！ 这点是本题最重要的  ）

显然 交集的最后一个匹配值为囊括了交集中所有匹配的（而这个值之前已经遍历过了!)

详情见代码

#include<bits/stdc++.h>

using namespace std;

//input

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define repp(i,a,b) for(int i=(a);i>=(b);i--)

#define RI(n) scanf("%d",&(n))

#define RII(n,m) scanf("%d%d",&n,&m);

#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)

#define RS(s) scanf("%s",s);

#define ll long long

#define inf 0x3f3f3f3f

#define REP(i,N)  for(int i=0;i<(N);i++)

#define CLR(A,v)  memset(A,v,sizeof A)

//////////////////////////////////

#define N 200000+5

#define mod 10007

string s,p;

int lens,lenp;

int nex[N];

int ans[N];

void getnext()

{

    nex[]=-;

    int k=-,j=;

    while(j<lenp)

    {

        if(k==-||p[j]==p[k])

            nex[++j]=++k;

        else k=nex[k];

    }

}

int main()

{

    int  cas;

    RI(cas);

    while(cas--)

    {

        RI(lenp);

        cin>>p;

        getnext();

        int cnt=lenp;

        rep(i,,lenp)

        {

            if(!nex[i])continue;

            if(nex[i]*<=i)

            {

                cnt++; ans[i]=; continue;

            }

           cnt++;

           cnt+=ans[nex[i]];

           ans[i]=+ans[nex[i]];

        }

        cout<<cnt%mod<<endl;

    }

    return ;

}

相关文章