Count the string---hdu3336（kmp Next数组的运用）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3336

题意就是求串s的前缀的个数和；

例如：abab

前缀个数

a 2

ab 2

aba 1

abab 1

总数：6

dp[i] 表示前面的字符以s[i-1]结尾的前缀个数；上列中dp[4]=2(以最后一个字符b结尾的前缀) {abab，ab}；

可以看出增加一个字母会产生一个新的前缀，那就是整个串，之前的前缀就是Next[i]的位置所对应的dp,即dp[Next[i]];

所以dp[i] = dp[Next[i]] + 1；-_-主要是仔细的想一下,有点绕；

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int N = 2e6+;

const int mod = ;

char s[N];

int dp[N], n, Next[N];

void GetNext()

{

    int i=,j=-;

    Next[] = -;

    while(i<n)

    {

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

            Next[++i] = ++j;

        else

            j = Next[j];

    }

}

int main()

{

    int T, sum;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &n);

        scanf("%s", s);

        GetNext();

        memset(dp, , sizeof(dp));

        sum = ;

        for(int i=; i<=n; i++)

        {

            dp[i] = dp[Next[i]] + ;

            sum = (sum + dp[i]) % mod;

        }

        printf("%d\n", sum);

    }

    return ;

}

巴特西

Count the string---hdu3336（kmp Next数组的运用）

最新文章

热门文章