hdu3366 Count the string

考虑dp[i]代表前缀s[1...i]出现的次数，必定有dp[nxt[i]] += dp[i]

倒着推就是了

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int T, n, nxt[200005], dp[200005], ans;

const int mod=10007;

char a[200005];

void mknxt(){

    int k=0;

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

        while(k && a[i]!=a[k+1])    k = nxt[k];

        if(a[i]==a[k+1])    nxt[i] = ++k;

    }

}

int main(){

    cin>>T;

    while(T--){

        ans = 0;

        scanf("%d", &n);

        scanf("%s", a+1);

        memset(nxt, 0, sizeof(nxt));

        for(int i=1; i<=n; i++)    dp[i] = 1;

        mknxt();

        for(int i=n; i>=1; i--)

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

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

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

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

    }

    return 0;

}

巴特西

hdu3366 Count the string

最新文章

热门文章