首页 > 代码库 > hdu 3336 Count the string（KMP）

hdu 3336 Count the string（KMP）

2024-07-16 10:00:39   219人阅读

 一道应用kmp算法中next数组的题目

这其中vis[i]从1加到n

vis[i]=[next[i]]+1;

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
char s[200005];
int b;
int next[200005];
int vis[200005];
void nest(char *s)
{
    next[0]=-1;
    int i=0;
    int j=-1;
    while(i<b)
    {
        if(j==-1||s[i]==s[j])
            {
                i++;
                j++;
                next[i]=j;
            }
        else
            j=next[j];
    }
   // for(i=0;i<=b;i++)
       // printf("%d\n",next[i]);
}
bool kmp(char *s)
{
    int sum=0;
    for(int k=1;k<=b;k++)
    {
        /*int i=0,j=0;
        while(i<b)
        {
            if(j==-1||s[i]==s[j])
            {
                i++;j++;
                if(j==k)
                {
                    sum++;  //printf("%d\n",j);
                    j=next[j];
                }
            }
            else j=next[j];
        }*/
        if(next[k]==0)
            vis[k]=1;
        else
            vis[k]=vis[next[k]]+1;
    }
}
int main()
{
   int a;
   scanf("%d",&a);
   while(a--)
   {
       memset(vis,0,sizeof(vis));
       scanf("%d",&b);
       scanf("%s",s);
        int sum=0;
        nest(s);
        kmp(s);
        for(int i=1;i<=b;i++)
            {sum+=vis[i];
            sum=sum%10007;}
       printf("%d\n",sum);
   }
}


联系
我们