当前位置:网站首页>最长回文子串(动态规划)

最长回文子串(动态规划)

2022-07-06 23:08:00 疯疯癫癫才自由

  最长回文子串:
    状态设计:dp[i][j]表示str[i]到str[j]的字串是否为回文子串,是表示为1,不是表示为0;
    状态转移方程:dp[i][j]=dp[i-1][j-1](str[i]==str[j])
                          = 0 (str[i]!=str[j]); 但此处又须注意,dp的值是以字符串的子串长度(1...len)进行递增枚举的,  而不是以字符下标i为基点,j=i+k(k=1...len),因为在算后面的dp[i][j]时,需要把dp[i-1][j-1]的值算出来,然而此时dp[i-1][j-1]时=是还没有算出来的,(脑补一下,就能想出来这个逻了);
    边界:dp[i][i]=1, dp[i][i+1]=1(str[i]==str[i+1]);

/**
    最长回文子串:
    状态设计:dp[i][j]表示str[i]到str[j]的字串是否为回文子串,是表示为1,不是表示为0;
    状态转移方程:dp[i][j]=dp[i-1][j-1](str[i]==str[j])
                          = 0 (str[i]!=str[j]);
                  但此处又须注意,dp的值是以字符串的子串长度(1...len)进行递增枚举的,
                  而不是以字符下标i为基点,j=i+k(k=1...len),因为在算后面的dp[i][j]时,
                  需要把dp[i-1][j-1]的值算出来,然而此时dp[i-1][j-1]时=是还没有算出来的
                  (脑补一下,就能想出来这个逻辑了);
    边界:dp[i][i]=1, dp[i][i+1]=1(str[i]==str[i+1]);
*/

/**
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cin >>str;
    int len=str.size();
    int dp[len][len]={0},ans=1;
    memset(*dp,0,sizeof dp);
    for(int i=0;i<len;++i)
    {
        dp[i][i]=1;
        if(i<len-1&&str[i]==str[i+1])
        {
            dp[i][i+1]=1;
            ans=2;
        }
    }
    for(int l=3;l<len;++l)
    {
        for(int i=0,j=0;i+l-1<len;++i)
        {
            j=i+l-1;
            if(str[i]==str[j]&&dp[i+1][j-1]==1)
            {
                dp[i][j]=1;
                ans=l;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
*/

然而,我们还可以把dp[i][j]表示的状态修改一下,以至于我们可以输出最长回文子串的内容。
    状态设计:dp[i][j]表示str[i]到str[j]的字串是否为回文子串,若是则这个值为此回文子串的长度,
    不是表示为0;
    状态转移方程:dp[i][j]=dp[i-1][j-1]+2 (str[i]==str[j])
                          = 0 (str[i]!=str[j]);
                  但此处又须注意,dp的值是以字符串的子串长度(1...len)进行递增枚举的,
                  而不是以字符下标i为基点,j=i+k(k=1...len),因为在算后面的dp[i][j]时,
                  需要把dp[i-1][j-1]的值算出来,然而此时dp[i-1][j-1]时=是还没有算出来的
                  (脑补一下,就能想出来这个逻辑了);


    边界:dp[i][i]=1, dp[i][i+1]=2(str[i]==str[i+1]);

/**
    然而,我们还可以把dp[i][j]表示的状态修改一下,以至于我们可以输出最长回文子串的内容。
    状态设计:dp[i][j]表示str[i]到str[j]的字串是否为回文子串,若是则这个值为此回文子串的长度,
    不是表示为0;
    状态转移方程:dp[i][j]=dp[i-1][j-1]+2 (str[i]==str[j])
                          = 0 (str[i]!=str[j]);
                  但此处又须注意,dp的值是以字符串的子串长度(1...len)进行递增枚举的,
                  而不是以字符下标i为基点,j=i+k(k=1...len),因为在算后面的dp[i][j]时,
                  需要把dp[i-1][j-1]的值算出来,然而此时dp[i-1][j-1]时=是还没有算出来的
                  (脑补一下,就能想出来这个逻辑了);
    边界:dp[i][i]=1, dp[i][i+1]=2(str[i]==str[i+1]);
*/

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    string str;
    cin >>str;
    int len=str.size();
    int dp[len][len]={0},ans=1;
    memset(dp,0,sizeof(dp));
    for(int i=0;i<len;++i)
    {
        dp[i][i]=1;
        if(i<len-1&&str[i]==str[i+1])
        {
            dp[i][i+1]=2;
            ans=2;
        }
    }
    for(int l=3;l<=len;++l)
    {
        for(int i=0,j=0;i+l-1<len;++i)
        {
            j=i+l-1;
            if(str[i]==str[j]&&dp[i+1][j-1]!=0)
            {
                dp[i][j]=dp[i+1][j-1]+2;
                ans=l;
            }
        }
    }
    int l=0,r=0,imax=0;
    for(int i=0;i<len;++i)
        for(int j=0;j<len;++j)
        {
            if(dp[i][j]>imax)
            {
                imax=dp[i][j];
                l=i;
                r=j;
            }
        }
    cout << ans << endl;
    cout <<imax << endl;
    for(;l<=r;++l)
        cout << str[l];
    return 0;
}

更高效的应当是二分加字符串hash的做法,这个写完,等明天有时间再温习一遍字符串hash,已是有点模糊了。

在写这个代码的时候,发现了一个跟好玩的事情:

即当数组不是全局变量时:
            如果数组大小是变量,则数组初始化为0时,元素的值也许不是0;
            如果数组大小是常量,则数组初始化为0时,元素的值是0;


/**
    当数组不是全局变量时:
            如果数组大小是变量,则数组初始化为0时,元素的值也许不是0;
            如果数组大小是常量,则数组初始化为0时,元素的值是0;
*/

/**
#include <iostream>
using namespace std;
const int maxn=10;
int main()
{
    cout << "数组大小是变量:\n";
    cout << "输入两个值:\n";
    int n, m;
    cin >> n >> m;
    int temp[n][m]={0};
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            cout << temp[i][j] << ' ';
    cout << "\n数组大小是const 类型的常量:\n";
    int matr[maxn][maxn]={0};
    for(int i=0;i<maxn;++i)
        for(int j=0;j<maxn;++j)
            cout << matr[i][j] << ' ';
    cout << "\n数组大小就是 common 常量:\n";
    int a[10][10]={0};
    for(int i=0;i<10;++i)
        for(int j=0;j<10;++j)
        cout << a[i][j] << ' ';
}
*/

 下面是这个程序的运行结果:

 

 

原网站

版权声明
本文为[疯疯癫癫才自由]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_51825761/article/details/125586254