最长对称子字符串

givenString =input()
def isReverse(s):
    return s ==''.join(reversed(s))
answer =""
for i in range(len(givenString)+1):
    for j in range(i):
        target = givenString[j:i]
        if isReverse(target) and len(target) > len(answer):
            answer =target
 
print(answer)

//动态规划，转移方程:
//dp[i][j]=dp[i+1][j-1]&&str[i]==str[j] (i+1<=j-1)
//dp[i][j]=str[i]==str[j]
#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    int x=0,y=0;
    cin>>str;
    vector<vector<bool>> dp(str.size(),vector<bool>(str.size(),false));
    for(int i=0;i<str.size();i++)
        dp[i][i]=true;
    for(int k=1;k<str.size();k++){
        int j=k,i=0;
        while(j<str.size()&&i<str.size()){
            if(i+1<=j-1)
                dp[i][j]=dp[i+1][j-1]&&str[i]==str[j];
            else
                dp[i][j]=str[i]==str[j];
            if(dp[i][j]==true){
                x=i;
                y=j;
            }
            i++;
            j++;
        }
    }
    cout<<str.substr(x,y-x+1);
    return 0;
}

简单易懂的动态规划法

思路：

动态规划解法：

代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

string maxHui(string s)
{
    int len = s.length();
    if(len <= 1)
        return s;
    string s2 = s;
    reverse(s2.begin(), s2.end());
    vector<vector<int>> dp(len+1, vector<int>(len+1, 0));
    int res = 0, pos = 0;
    for(int i = 1; i <= len; i++)
    {
        for(int j = 1; j < len+1; j++)
        {
            if(s[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            if(res <= dp[i][j])
            {
                res=dp[i][j];
                pos = i-1;
            }
        }
    }
    return s.substr(pos-res+1, res);
}

int main()
{
    string str;
    while(getline(cin, str))
        cout << maxHui(str) << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

string mk_str(string s) {
    string temp = "$#";
    for (size_t i = 0; i < s.size(); i++) {
        temp = temp + s[i];
        temp = temp + "#";
    }
    return temp;
}

int main() {
    string str;
    cin >> str;
    str = mk_str(str);
    vector<int> len(str.size());
    int right = 0, max_len = 0, max_point = 0, pos = 0;
    for (size_t k = 1; k < str.size(); k++) {
        int i = k;
        len[i] = i < right ? min(right - i, len[2 * pos - i]) : 1;
        while(str[i + len[i]] == str[i - len[i]]) len[i]++;
        if (i + len[i] > right) {
            right = i + len[i];
            pos = i;
        }
        if (len[i] > max_len) {
            max_len = len[i];
            max_point = i;
        }
    }
    for (int i = max_point - max_len + 1; i <= max_point + max_len - 1; i++) str[i] == '#' || cout << str[i];
    cout << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s,t="";
    cin>>s;
    int n=s.length(), Max=0;
    for(int i=0;i<n-1;i++){
        int l=i,r=i+1;
        while(l>=0 && r<=n-1 && s[l--]==s[r++])
        if(r-l-1>Max){
            Max = r-l-1;
            t = s.substr(l+1, r-l-1);
        }
    }
    for(int i=1;i<n-1;i++){
        int l=i-1,r=i+1;
        while(l>=0 && r<=n-1 && s[l--]==s[r++])
        if(r-l-1>Max){
            Max = r-l-1;
            t = s.substr(l+1, r-l-1);
        }
    }
    if(t=="")
        cout<<s[0]<<endl;
    else
        cout<<t<<endl;
    return 0;
}

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main()
{
	string str;
	cin >> str;
	int n = str.size();
	pair<int, int> res = { 1, 0 };
	vector<vector<bool>> a(n , vector<bool>(n,false));
	for (int i = n - 1; i >= 0; i--) a[i][i] = true;
	for (int i = n - 1; i >= 0; i--)
	for (int j = i + 1; j < n; j++)
	{
		if (j == i + 1 && str[i] == str[j])
		{
			a[i][j] = true;
			if (j - i + 1 > res.first)
				res = { j - i + 1, i };
		}
		else if (j>i + 1 && str[i] == str[j] && a[i + 1][j - 1])
		{
			a[i][j] = true;
			if (j - i + 1 > res.first)
				res = { j - i + 1, i };
		}
	}
	string str_res = str.substr(res.second, res.first);
	cout << str_res << endl;
	return 0;
}

/*
求最长对称子串
考虑动态规划，设dp[x][y]为从x到y的子串是否对称，若对称表示长度，不对称为-1
子串长度从1到n遍历
当 dp[x+1][y-1] ！= -1 并且 s[x] == s[y] ，则 dp[x][y] = dp[x+1][y-1] + 2 ;
否则  dp[x][y] = -1
边界条件 x==y dp[x][y] = 1 ; x<y dp[x][y] = 0
*/
#include<bits/stdc++.h>
using namespace std;
#define N 10000

int main()
{
//    freopen("input.txt", "r", stdin);
    char s[N];
    cin >> s;
    int n = strlen(s);
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j + i < n; j++) {
            if(i == 0) dp[j][j] = 1;
            else {
                if(dp[j + 1][j + i - 1] == -1 || s[j] != s[j + i]) dp[j][j + i] = -1;
                else dp[j][j + i] = dp[j + 1][j + i - 1] + 2;
            }
        }
    }
    int ans = 0, x, y;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(dp[i][j] > ans) {
                ans = dp[i][j];
                x = i;
                y = j;
            }
    for(int i = x; i <= y; i++) {
        cout << s[i];
    }
    cout << endl;
    return 0;
}

因为给定一个字符串，只含数字或大小写字母，可以在每相邻字符之间添加'*'，就不用分aba和abba两种情况了。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        // 在每相邻两个字符之间添加‘*’
        str = str.replaceAll(".", "*$0").substring(1);
        int maxArea = 0, maxIndex = 0;
        for (int i = 0; i < str.length(); i++) {
            int temp = getArea(str, i);
            if (temp > maxArea) {
                maxArea = temp;
                maxIndex = i;
            }
        }
        System.out.println(str.substring(maxIndex - maxArea, maxIndex + maxArea + 1).replace("*", ""));
    }

    private static int getArea(String str, int index) {
        int area = 0;
        int left = index - 1, right = index + 1;
        while (left >= 0 && right <= str.length() - 1) {
            // 向左右两边扩展
            if (str.charAt(left--) == str.charAt(right++)) {
                area++;
            } else {
                break;
            }
        }
        return area;
    }
}

有些人没仔细看，晚、安的方法并没有问题。但是它的方法遍历了所有的子字符串，这个工作量是最大的，字符越多压力增加得越快，代码还可以优化，其实可以及时的break出来的。
我的思路是，回文无非两种可能，偶数类对称和奇数类对称，那我从最小的回文开始往外扩大，就没有漏洞了。

排除极端情况单个字母，余下的情况就是一个for循环从左往右遍历，回文的起点不是aa就是aba，所以我先找起点，之后往外圈一次次判断就完了，一旦不符合条件跳出循环对比长度选择保存，然后下一个循环即可，所以就是一个for套一个while。代码是边提交边修补写的，很烂，主要是为了过关答题。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main(){
    string str,tmp,max,rev;
    while(cin >> str){
        max=str[0];
        for(int i=0;i<str.length();i++){
            for(int j=str.length();j>i;j--){
                if(str[i]==str[j]){
                    rev=str.substr(i,j+1-i);
                    tmp= rev;
                    reverse(rev.begin(),rev.end());
                    if(tmp == rev)
                        if(tmp.length()>max.length()){
                            max=tmp;
                            break;
                        }
                }
            }
        }
        cout << max;
    }
    return 0;
}

JavaScript，当时并没有成功，当时忘记reverse()把原数组也会反转，现在测试是可以的，有改进和错误请告诉我，万分感谢

function findLonglestSubStr(str){
    // 将字符串转换为数组
    let arr=str.split('');
    let result=[];

    // 对长度为0和1的字符串直接返回
    if(arr.length<2) return arr.join('');

    for(let i=0;i<arr.length;i++){
        // 从arr截取下标i到结尾的数组给arr2
        let arr2=arr.slice(i);

        // 找到以该字母为起始点的最长回文串
        while(arr2.join('')!==[...arr2].reverse().join('')){
            arr2.pop();
        }
        
        /* 
        如果最终这个数组剩下超过1的长度，而且比最终要返回的结果数组长度要大，则返回结果数组指向这个回文数组
        */
        if(arr2.length!==1 && arr2.length>result.length) result=arr2; 
    }
    return result.join('');
}

console.log(findLonglestSubStr('abbaad')); // abbaa
console.log(findLonglestSubStr('a')); // a
console.log(findLonglestSubStr('abccbd')); //bccb

var line=readline();                        //读取输入字符串
var len=line.length;
function reverseStr(str){                   //反转字符串
    return str.split("").reverse().join("");
}
function getSymmetry(str){                  
    var maxSubString="";
    for(var i=0;i<len;i++){                  //两for循环获得子字符串
        for(var j=len;j>i;j--){              //并判断获取的子字符串是否是对称字符串
            var temp=str.substring(i,j);
            if(temp===reverseStr(temp) && maxSubString.length<temp.length){
                maxSubString=temp;
            }
        }
    }
    return maxSubString;
}
if(len==1){
    console.log(line)
}else{
    console.log(getSymmetry(line));
}

#include<bits/stdc++.h>
using namespace std;
bool isTrue(string str){
    int len=str.size();
    for(int i=0;i<=len/2;i++){
        if(str[i]!=str[len-i-1]){
            return false;
        }
    }
    return true;
}
int main(){
    string str;
    cin>>str;
    int len=str.size();
    if(len==1){
        cout<<str<<endl;
    }else if(len==2){
        if(str[0]==str[1]){
            cout<<str<<endl;
        }else{
            cout<<str[0]<<endl;
        }
    }else{
        string maxString="";
        int first=0,end=len;
        for(int i=0;i<len;i++){
            for(int j=len;j>i;j--){
                string temp=str.substr(i,j);
                if(isTrue(temp)){
                    if(temp.size()>maxString.size()){
                        maxString=temp;
                    }
                }
            }
        }
        cout<<maxString<<endl;
    }
    return 0;
}

这个题是LeetCode的第5题 最长回文子串，算是第二次遇到，但是我写的还是比人家的答案长得多，乱得多。
思路是：先确定中心再向两边延伸，回文串有两种：
①中心的两个字符是一样的，如"abccba"；
②中心只有一个字符，如"abcba"。

所以针对两种情况要分别来求：
①针对第一种，每个字符都可以是中心；
②针对第二种，必须先找到"cc"，即通过s[i] == s[i - 1]这样的判断找到两个c中的某一个，然后向两边延伸着找。

下面是LeetCode一个写的比较简洁的答案：

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        System.out.println(solve(input));
    }

    public String solve(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

所有的答案里面居然没有用O(n)复杂度的manacher算法。。。都是O(n^2)的暴力解法。。下面我提供一个AC了的manacher方法，供大家参考，如果是笔试O(n^2)的复杂度能AC那也ok，如果是面试，让你提供一个O(n)复杂度的找最长回文子串的算法，希望能想到是用manacher算法

import java.util.Scanner;
import static java.lang.System.in;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        String str = sc.nextLine();
        System.out.println(manacherProcess(str));
    }

    public static char[] manacherStr(String str) {
        char[] arr = str.toCharArray();
        char[] manArr = new char[arr.length * 2 + 1];
        for (int i = 0, j = 0; i < manArr.length; i++) {
            manArr[i] = (i & 1) == 0 ? '#' : arr[j++];
        }
        return manArr;
    }

    public static String manacherProcess(String str) {
        char[] manArr = manacherStr(str);
        int[] pArr = new int[manArr.length];
        int index = -1;
        int pR = -1;
        int maxVal = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int i = 0; i < pArr.length; i++) {
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
            while (i + pArr[i] < manArr.length && i - pArr[i] > -1) {
                if (manArr[i + pArr[i]] == manArr[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                index = i;
            }
            if (pArr[i] > maxVal) {
                maxVal = pArr[i];
                maxIndex = i;
            }
        }
        String ret = "";
        for (int i = maxIndex - maxVal + 1; i < maxIndex + maxVal; i++) {
            ret += (i & 1) == 0 ? "" : manArr[i];
        }
        return ret;
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        String input = sc.nextLine();
        System.out.println(func(input));
    }
     public static String func(String s) {
         int begin=0;
         int end=0;
         for(int i=0;i<s.length();i++){
             int[] l1=a(s,i,i);
             int[] l2=a(s,i,i+1);
             if(l1[1]-l1[0]>end-begin)
                 {end=l1[1];
                  begin=l1[0];
             }
             if(l2[1]-l2[0]>end-begin)
                   {end=l2[1];
                  begin=l2[0];
             }
         }
         return s.substring(begin,end+1);
     }
    public static int[] a(String s ,int begin,int end){
        while(begin>=0&&end<s.length()&&s.charAt(begin)==s.charAt(end)){
            begin--;
            end++;
        }
        //找到回文，返回最后一次迭代前的状态
        return new int[]{begin+1,end-1};
    }
}