最长回文子串（动态规划）

  最长回文子串：
    状态设计：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] << ' ';
}
*/

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