POJ 3336 Count the string （KMP+DP，好题）

参考连接：

KMP+DP：

http://www.cnblogs.com/yuelingzhi/archive/2011/08/03/2126346.html

另外给出一个没用dp做的：
http://blog.sina.com.cn/s/blog_82061db90100usxw.html

题意：

　　给出一个字符串，求它的各个前缀在字符串中出现的次数总和。

思路：
记 dp[i] 为前 i 个字符组成的前缀出现的次数
则 dp[next[i]]+=dp[i]

dp[i]表示长度为i的前缀出现的次数，初始条件dp[i]=1，即至少出现一次。
举例：
index:012345
ababa
next: 000123
dp[5]=1;
dp[4]=1;
i=5:dp[3]=dp[3]+dp[5]=2;
i=4:dp[2]=dp[2]+dp[4]=2;
i=3:dp[1]=dp[1]+dp[3]=3;
即各前缀出现次数：
a:3
ab:2
aba:2
abab:1
ababa:1

至于如何理解状态方程dp[next[i]]+=dp[i]，看下面那张图：

设前缀s长度为i，在字符串中出现的次数为3次，即为图中的s1,s2,s3。
图中红色部分即为前缀与后缀相同的子串，长度为next[i]。
设为p1,p2,p3,p4（其中p2,p3各为两次重叠）
可以知道，p1即为一开始初始化时算入进去的1，而p2,p3,p4正好对应s1,s2,s3，即s在字符串中出现的个数dp[i]。
这样状态转移方程就好理解了。
dp[next[i]]=dp[next[i]]+dp[i]。

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <string>

#include <string.h>

using namespace std;

const int maxn=;

const int mod=;

int n;

char str[maxn];

int next[maxn];

int dp[maxn]; //dp[i]表示长度为i的前缀出现的次数

int len,L,l,num;

void getNext(char*str){

    int k=,lm=strlen(str);

    next[]=;

    for(int i=;i<lm;i++){

        while(k> && str[k]!=str[i])

            k=next[k];

        if(str[k]==str[i])

            k++;

        next[i+]=k;

    }

}

int main()

{

    int t;

    char tmp[maxn];

    scanf("%d",&t);

    while(t--){

        scanf("%d",&len);

        scanf("%s",str);

        getNext(str);

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

            dp[i]=;  //初始均为1

        for(int i=len;i>=;i--){

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

        }

        int ans=;

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

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

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

    }

    return ;

}

巴特西

POJ 3336 Count the string （KMP+DP，好题）

最新文章

热门文章