【HDU 3336 Count the string 】 KMP

HDU3336

本題題意為求字元串的每個字首在整個字元串中的出現次數。

如果next[j]對答案有一個貢獻，那麼這個貢獻在j中一定會再貢獻一次，而且j為結尾的字元串對于總串産生的貢獻隻有長度為j的子串，（如果這個性質不懂，可以去看我的KMP總結專題性質二）于是我們可以得到轉移方程 ans[j]=ans[next[j]]+1 a n s [ j ] = a n s [ n e x t [ j ] ] + 1 ，最後對所有字首的貢獻取和即為答案。

HDU3336代碼

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stack>
using namespace std ;
const int maxn = +;
int Next[maxn];
char str[maxn];
char mo[maxn];
int dp[maxn];
int n1,n2;
void GetNext()
{
    int i=,j=-;
    while(i<n2)
    {
        if(j==-||mo[i]==mo[j]) {++i,++j,Next[i]=j;}
        else j=Next[j];
    }
    return ;
}
int kmp()
{
    int cnt=;
    int i=,j=;
    while(i<n1)
    {
        if(j==-||str[i]==mo[j]) i++,j++;
        else j=Next[j];
        if(j==n2)
        {
            cnt++;
            j=;
        }
    }
    return cnt;
}
int ans[maxn];
int main()
{
    int cnt;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%s",&n2,mo);
        Next[]=-;
        GetNext();
        int ans=;
        dp[]=;
        for(int i=;i<=n2;i++)
        {
            dp[i]=dp[Next[i]]+;
            ans=(ans+dp[i])%;
        }
        printf("%d\n",ans);
    }
    return ;
}