[HDU 3336]Count the String[kmp][DP] - c++编程基础

题意:

求一个字符串的所有前缀串的匹配次数之和.

思路:

首先仔细思考: 前缀串匹配.

n个位置, 以每一个位置为结尾, 就可以得到对应的一个前缀串.

对于一个前缀串, 我们需要计算它的匹配次数.

k = next [ j ]

表示前缀串 Sj 的范围内(可以视为较小规模的子问题), 前缀串 Sk 是最长的&能够匹配两次的前缀串.

这和我们需要的答案有什么关系呢

题目是求所有前缀串的匹配次数之和, 那么可以先求前缀串 Si 在整个串中的匹配次数, 再加和.

到此, 用到了两个"分治", 一是将大规模的问题减小为小规模的问题, 二是将询问的最终结果拆分成一个个步骤, 则专注于分析核心步骤.

可设dp[ i ]为前缀串 Si 在总串中出现的次数.

dp[i] = 1;

dp[next[i]] += dp[i];

#include   
#include   
const int MAXN = 200005;  
const int MOD = 10007;  
int dp[MAXN],next[MAXN];  
char s[MAXN];  
//46MS  1960K  
void prekmp()  
{  
    next[0] = -1;  
    int j = -1;  
    for(int i=1;s[i];i++)  
    {  
        while(j!=-1 && s[j+1]!=s[i])    j = next[j];  
        if(s[j+1]==s[i])    j++;  
        next[i] = j;  
    }  
}  
  
int main()  
{  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        int n;  
        scanf("%d",&n);  
        scanf("%s",s);  
        prekmp();  
        for(int i=0;i

还有另一种思路:

可以将前缀的匹配次数视为包含的前缀个数.

最终的问题是求s中 (设每一种前缀i包含的前缀个数Fi ) ΣFi .

dp[i]为前缀串s[0...i]包含的前缀个数的新增数目(相对于前缀串s[0...i-1]).

则

dp[i] = dp[next[i]] + 1;//1表示它本身也是新增的一个前缀

#include   
#include   
const int MAXN = 200005;  
const int MOD = 10007;  
int dp[MAXN],next[MAXN];  
char s[MAXN];  
//62MS  1960K  
void prekmp()  
{  
    next[0] = -1;  
    int j = -1;  
    for(int i=1;s[i];i++)  
    {  
        while(j!=-1 && s[j+1]!=s[i])    j = next[j];  
        if(s[j+1]==s[i])    j++;  
        next[i] = j;  
    }  
}  
  
int main()  
{  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        int n;  
        scanf("%d",&n);  
        scanf("%s",s);  
        prekmp();  
        memset(dp,0,sizeof(int)*(n+1));  
        for(int i=0;i