题意:

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

思路:

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

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

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

k = next [ j ]

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

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

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

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

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

dp[i] = 1;

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

#include <cstring>

#include <cstdio>

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<n;i++)    dp[i] = 1;

        dp[n] = 0;

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

        {

            if(next[i]!=-1) {dp[next[i]] += dp[i];dp[next[i]] %= MOD;}

        }

        for(int i=0;i<n;i++)    {dp[n] += dp[i];dp[n] %= MOD;}

        printf("%d\n",dp[n]);

    }

}

还有另一种思路:

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

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

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

则

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

#include <cstring>

#include <cstdio>

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<n;i++)

        {

            if(next[i]!=-1)

            {

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

                dp[i] %= MOD;

            }

            else

                dp[i] = 1;

        }

        for(int i=0;i<n;i++)    {dp[n] += dp[i];dp[n] %= MOD;}

        printf("%d\n",dp[n]);

    }

}