题意:

给定一个长度不超过1000的字符串,求它的回文子串串的数量mod10007。

分析:

我们知道如果求最长回文子串,我们可以做到O(n2)求解。如何做到的呢?如果用s[i]表示字符串第i位的字符,f(i,j)表示从i到j的子串中回文子串的最长长度,那么
$$
f(i,j)=max\begin{cases}
f(i+1,j)\\
f(i,j-1) \\
f(i+1,j-1) +1 & \text{(s[i]==s[j])}
\end{cases}
$$
我们发现求最长回文子串是分s[i]==s[j]与否进行转移的。
如果是求回文子串数呢?
经过思考,我们会发现,如果s[i]!=s[j],i,j之间的回文子串只有可能出现在s[i…j-1]或s[i+1…j]这两个区间中。由于这两个区间有重复部分[i+1…j-1],所以我们不妨像容斥原理那样将中间的减去。
如果s[i]==s[j]呢?i,j之间的回文子串又有了更多可能:除了s[i]!=s[j]的情况之外,还出现了s[i…j]区间中的,以及s[i]s[j]组成的回文串。所以我们可以列出状态转移方程:
$$
f(i,j)=max\begin{cases}
f(i+1,j) + f(i,j-1) – f(i+1,j-1) & \text{(s[i]!=s[j])} \\
f(i+1,j) + f(i,j-1) + 1& \text{(s[i]==s[j])}
\end{cases}
$$
所以我们就可以获得代码:

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 1005

using namespace std;

int f[MX][MX],n;
char s[MX];


int work()
{
    int len=strlen(s);
    memset(f,0,sizeof(f));
    for(int i=0;i<len;i++)f[i][i]=1;
    for(int i=1;i<len;i++)
        for(int j=0;j+i<len;j++)
            if(s[j]!=s[j+i])f[j][j+i]=(f[j][j+i-1]+f[j+1][j+i]-f[j+1][j+i-1]+10007)%10007;
            else f[j][j+i]=(f[j][j+i-1]+f[j+1][j+i]+1)%10007;
    return f[0][len-1];
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int w=1;w<=t;w++)scanf("%s",s),printf("Case %d: %d\n",w,work());
    return 0;
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *