16行 AC (C++)

#include <iostream>
using namespace std;
int main() {
    string s;
    getline(cin,s);
    int sum1, sum2, ans = 0;
    for(int i = 0; i < s.length(); i++) {
        sum1 = sum2 = 0;
        int j = i + 1;
        while(i - sum1 >= 0 && i + sum1 < s.length() && s[i-sum1] == s[i+sum1]) sum1++;//长度为奇数 
        while(i - sum2 >= 0 && j + sum2 < s.length() && s[i-sum2] == s[j+sum2]) sum2++;//长度为偶数 
        ans = max(ans, max(2*sum1 - 1, 2 * sum2));
    }
    cout << ans;
    return 0;
}

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string str; getline(cin, str); int len = str.length();
    int maxLen=0, tmpLen;
    // 奇对称
    for(int i=0; i<len; i++) {
        tmpLen = 1;
        while((i-tmpLen)>=0 && (i+tmpLen)<len) {
            if(str[i-tmpLen] == str[i+tmpLen]) {
                tmpLen++;
            } else {
                break;
            }
        }
        if((2*tmpLen-1) > maxLen) {
            maxLen = 2*tmpLen - 1;
        }
    }
    // 偶对称
    for(int i=0; i<len; i++) {
        tmpLen = 1;
        while((i-tmpLen+1)>=0 && (i+tmpLen)<len) {
            if(str[i-tmpLen+1] == str[i+tmpLen]) {
                tmpLen++;
            } else {
                break;
            }
        }
        if((2*tmpLen-2) > maxLen) {
            maxLen = 2*tmpLen - 2;
        }
    }
    cout << maxLen << endl;
    return 0;
} 

最长回文子串如果采用暴力求解的方法，枚举端点的时间复杂度为$O(n^2)$,判断回文的时间复杂度为$O(n)$， 总的时间复杂度为$O(n^3)$,这样的事件复杂度很容易超时, 但是如果采用动态规划的方法可以将时间复杂度降低到$O(n^2)$.

令$dp[i][j]$表示S[i]到S[j]的子串是否是回文子串,是则为1,否则为0,那么就有:

• 如果$S[i] == S[j]$, 那么只要$S[i+1]$到$S[j-1]$之间是回文子串的话, 那么$S[i]$到$S[j]$也是回文子串

• 如果$S[i] != S[j]$, 那么$S[i]$到$S[j]$之间肯定不是回文子串

  状态转移方程为：

  dp[i][j]=dp[i+1][j-1],if(S[i] == S[j]) or 0 if(S[i] != S[j])

  边界条件:

  $dp[i][i] = 1, dp[i][i+1] = (S[i] == S[j]) ? 1 : 0$

#include 
#include 
#include 
using namespace std;
const int maxn = 1000 + 10;
int dp[maxn][maxn];
int main() {
  string line;
  getline(cin, line);
  int ans = 1;
  memset(dp, 0, sizeof(dp));
  for (int i = 0; i  //初始化边界条件
    dp[i][i] = 1;
    if (i < line.size() - 1) {
      if (line[i] == line[i + 1]) {
        dp[i][i + 1] = 1;
        ans = 2;
      }
    }
  }
  for (int l = 3; l  //由于在处理边界条件的时候我们已经处理了子字符串长度为1或2的情况，所以这个时候从3开始枚举
    for (int i = 0; i + l - 1 < line.size(); i++) {  //枚举左端结点
      int j = i + l - 1;
      if (line[i] == line[j] && dp[i + 1][j - 1] == 1) {
        dp[i][j] = 1;
        ans = l;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}

a,m = input(),[0,0,1,1]                 # m[2]记偶数最大回文字符串，m[3]记奇数
for i in range(2,4):                    # 2为偶数最短测试长度，3为奇数
    k = j = 0                           # k为测试长度的一半，j为指针索引
    while j <= len(a) - i - k * 2:
        if a[j:j + i + k * 2] == a[j:j + i + k * 2][::-1]:
            l = 1
            while l <= min(j,len(a) - j - i - k * 2):
                if a[j - l:j + i + k * 2 + l] != a[j - l:j + i + k * 2 + l][::-1]:
                    break
                l += 1
            k += l
            m[i] = 2 * k + i - 2 if 2 * k + i - 2 > m[i] else m[i]
        else:
            j += 1
print(max(m))

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 110010;
char Ma[MAXN * 2];
int Mp[MAXN * 2];
void Manacher (char s[], int len)
{
    int l = 0;
    Ma[l++] = '$';
    Ma[l++] = '#';
    for (int i = 0; i < len; i++)
    {
        Ma[l++] = s[i];
        Ma[l++] = '#';
    }
    Ma[l] = 0;
    int mx = 0, id = 0;
    for (int i = 0; i < l; i++)
    {
        Mp[i] = mx > i ? min (Mp[2 * id - i], mx - i) : 1;
        while (Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++;
        if (i + Mp[i] > mx)
        {
            mx = i + Mp[i];
            id = i;
        }
    }
}
char s[MAXN];
int main()
{
    while (gets(s))
    {
        int len = strlen (s);
        Manacher (s, len);
        int ans = 0;
        for (int i = 0; i < 2 * len + 2; i++)
            ans = max (ans, Mp[i] - 1);
        printf ("%d\n", ans);
    }
    return 0;
}

解决问题

       思路：从0号位向后搜索，按照长度为一到最大枚举，将字串取出，反向后与原串比较，若近似且长度大于当前最大值更新，最后得到答案

译文描述

给定一个字符串，您应该输出最长的对称子字符串的长度。例如，给定“ PAT＆TAP对称吗？”，最长的对称子字符串是“ s PAT＆TAP s”，因此您必须输出11。

输入描述

每个输入文件包含一个测试用例，该用例给出的长度不超过1000的非空字符串。

输出描述

对于每个测试用例，只需在一行中打印最大长度即可。

输入例子

PAT＆TAP是对称的吗？

输出例子

11

代码实现

#include <bits / stdc ++。h>

使用命名空间std;

字符串str，temp;

int main（）

{

    getline（cin，str）;

    int _max = 0;

    for（int i = 0; i <str.length（）; i ++）

    {

        for（int j = 1; j <= str.length（）-i; j ++）

        {

            现在的字符串= str.substr（i，j）;

            temp = now;

            反向（temp.begin（），temp.end（））;

            如果（现在==临时）

            {

                如果（j> _max）

                {

                    _max = j;

                }

            }

        }

    }

    cout << _ max;

    返回0;

给一个字符串 计算这个字符串内的最长的 回文串的长度。题目很简单，这道题首先想到的应该就是暴力解法。但是暴力解法 判断是否是回文O(n^2) 再加上整个串就是O(n^3) 可能会超时。

于是想到用动态规划来做，下面我将给出一个完整的思路过程，我也是这两天初学动态规划。思考了这个问题一些时间，希望能给到初学的同学一些帮助，同时也作为自己学习的一些笔记。

思路

我们先来看一种最简单的情况。

如果有字符串A-B-A 那么这个字符串是回文串。

可以如何判断呢？ 如果是想C语言老师讲的方法 可以从两端往中间判断是否相等

for(int i=0;i<len/2;i++)
    if(s[i]！=s[len-i-1])return false

这样就能判断出来A-B-A 是回文串。

如果该串变成 A-A-B-A-A 。

case 1： 两端加上的字符相等 且 内部包含的 A-B-A 是回文串

这时候就可以利用之前计算过的A-B-A 的结果。 A-A-B-A-A 是回文串。且长度为3+2=5；

case 1： 两端加上的字符不相等

例如A-A-B-A-C 这时候就需要判断 A-A-B-A 和A-B-A-C 中最大的那个结果就是A-A-B-A-C 串的最大回文串！。

动规模型

开辟一个大二维数组:

#define MAX 1010
int dp[MAX][MAX]; //dp[ i ][ j ] 表示从i 到 j 的字符串中的最长的回文串 
bool dp_b[MAX][MAX];//dp[ i ][ j ] 表示从i 到 j 的字符串是否是回文串

由上述的 关系得到 递推式 状态转移方程

边界条件

1. 当i==j的时候 也就是只有一个字符的时候 长度是1

2. 同时我们默认是正序，所以 当i<j 的时候 是0

   例如字符串ABCBA
   

   我们对dp二维数组从左下到右上的遍历计算。

当二维数组计算完成之后右上角的值就是整个字符串的最大回文数的结果。

AC代码

#include <string>
   #include <cstring>
   #include <iostream>
   #include <algorithm>
   using namespace std;
   #define MAX 1010
   int dp[MAX][MAX];
   bool dp_b[MAX][MAX];
   string s;
   int main(int argc, char const *argv[])
   {
       getline(cin,s);
       memset(dp,0,sizeof(dp));memset(dp_b,false,sizeof(dp_b));
       for(int i=0;i<s.length();i++){ //初始化边界条件
            dp[i][i]=1; 
            dp_b[i][i]=true;     
       }
       for(int j =1;j<s.length();j++){//状态转移方程
           for(int i =j-1;i>=0;i--){
               if(s[i]==s[j]&&i+1==j){//这个处理 当两个连在一起的相同字符
                       dp_b[i+1][j-1] =true;
                       dp_b[i][j]=true;
               }
               if(s[i]==s[j]&&dp_b[i+1][j-1]){//两端相等且内部是回文串
                       dp[i][j] =dp[i+1][j-1]+2;//长度加2
                       dp_b[i][j]=true;
               }
               else{
                   dp[i][j] =max(dp[i][j-1],dp[i+1][j]);//两端不会回文串计算
               }                                        //左右两个子串
           }
       }
       cout<<dp[0][s.length()-1];//输出最终结果
       return 0;
   }

使用动规 可以将时间复杂度降到O(n^2) 。

        #include

        #include

        using namespace std;

        const int maxn=1010;

        char S[maxn];

        int dp[maxn][maxn];

        int main(){

        gets(S);

        int len = strlen(S),ans=1;

        memset(dp,0,sizeof(dp));

        for(int i=0;ilen;i++){

        dp[i][i]=1;

        if(ilen-1){

        if(S[i]==S[i+1]){

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

        ans=2;

        }

        }

        }

        //状态转移

        for(int L=3;Llen;L++){

        for(int i=0;i+L-1len;i++){

        int j=i+L-1;

        if(S[i]==S[j] && dp[i+1][j-1]==1){

        dp[i][j]=1;

        ans = L;

        }

        }

        }

        printf("%d\n",ans);

        return 0;

        }

s=input()
F,res=[[False]*len(s) for _ in range(len(s))],0
for length in range(1,len(s)+1):
    for i in range(len(s)-length+1):
        j=i+length-1
        F[i][j]=(s[i]==s[j] and (j-i<2 or F[i+1][j-1]))
        res=max(res,j-i+1) if F[i][j] else res
print(res) 

思路： 这个还是使用了 散列表的思想做，找出 字符串所在的所有位置，然后遍历这些位置
比如 PATAP ,p的位置在 0 4， 向内部扩展看1 3是否相等，向等就加上2 ，向外扩展越界，就
不在查看了。
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

#ifndef debug
ifstream ifile("case.txt");
#define cin ifile
#endif

int Reverse(vector<bool> &mark, string & str, int a, int b)// 开始点和对称点 a < b
{
    //if (mark[a] && mark[b])
    //    return -1;// 代表已经查找过了
    int count = 0;
    int c = a-1;
    int d = b+1;
    for (; a <= b; a++, b--)// 向内扩展
    {
        if (str[a] == str[b] && a<b)
        {
            mark[a] = true;
            mark[b] = true;
            count+=2;
        }
        else if (str[a] == str[b] && a == b)
        {
            count++;
        }
        else
        {
            break;
        }
    }
    for (; c >= 0 && d < str.size(); c--, d++)//向外扩展
    {

        if (str[c] == str[d])
        {
            mark[c] = true;
            mark[d] = true;
            count += 2;
        }
        else
            break;
    }
    return count;
}


int main()
{
    map<char, vector<int> > mp;
    string str;
    getline(cin, str);
    vector<bool> mark(str.size(), false);
    for (int i = 0; i < str.size(); i++)
    {
        mp[str[i]].push_back(i);
    }
    int maxLen = 0;
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        if (it->second.size() < 2)
            continue;
        //sort(it->second.begin(), it->second.end());
        for (int i = 0; i < it->second.size(); i++)
        {
            for (int j = i+1; j < it->second.size(); j++)
            {
                // 看是否有回文字符串
                int t = Reverse(mark, str, it->second[i], it->second[j]);
                if (t > maxLen)
                {
                    maxLen = t;
                }    
            }
        }
    }
    cout << maxLen << endl;
    system("pause");
}

s = input()
def sym(t):
    i, j = 0, len(t)-1
    while i<j:
        if t[i]!=t[j]: return False
        i, j = i+1, j-1
    return True

ans, n, lo = 1, len(s), 0
while lo+ans<n:
    for j in range(n-1,lo+ans,-1):
        if sym(s[lo:j+1]):
            ans = max(ans,j-lo+1)
            break
    lo += 1

print(ans)    

#include "iostream"
#include "vector"
#include "string"
#include "cstring"
#include "queue"
#include "stack"
#include "map"
#include "ctime"
#include <limits.h>
#include <algorithm>
using namespace std;

const int maxn = 1010;
int RL[maxn * 2];

vector<char> str;
int main()
{
	char temp;
	str.push_back('#');
	while (1)
	{
		temp = getchar();
		if (temp == '\n')
			break;
		str.push_back(temp);
		str.push_back('#');
	}

	int MaxRight = 0, pos = 0, maxLen = 0;
	for (int i = 0; i < str.size(); ++i)
	{
		if (i < MaxRight)
			RL[i] = min(RL[2 * pos - i], MaxRight - i);
		else
			RL[i] = 1;

		while (i - RL[i] >= 0 && i + RL[i] < str.size() && str[i - RL[i]] == str[i + RL[i]])
			RL[i] += 1;
		if (RL[i] + i - 1 > MaxRight)
		{
			MaxRight = RL[i] + i - 1;
			pos = i;
		}
		if (RL[i] > maxLen)
			maxLen = RL[i];
	}
	cout << maxLen - 1;
}

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1010;
int dp[maxn][maxn];
char s[maxn];
int main(){
	gets(s);
	int len=strlen(s);
	int ans=1;
	memset(dp,0,sizeof(dp));
	for(int i=0;i<len;i++){
		dp[i][i]=1;
		if(i<len-1){
			if(s[i]==s[i+1]){
				dp[i][i+1]=1;
				ans=2;
			}
		}
	}
	for(int L=3;L<=len;L++){
		for(int i=0;i+L-1<len;i++){
			int j=i+L-1;
			if(s[i]==s[j] && dp[i+1][j-1]==1){
				dp[i][j]=1;
				ans=L;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}