回文串

[编程题]回文串

热度指数：536 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

回文串是指字符串无论从左读还是从右读，所读的顺序是一样的；简而言之，回文串是左右对称的。

现给定一个字符串，求出它的最长回文子串。你可以假定只有一个满足条件的最长回文串。

输入描述:

一行, 字符串

输出描述:

一行, 字符串

示例1

输入

yabccbau

输出

abccba

算法知识视频讲解

pein531

从最长的开始，穷举所有子串，并验证其回文性即可

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine().trim();
        for(int len = str.length(); len >= 1; len--){
            for(int i = 0; i <= str.length() - len; i++){
                String substr = str.substring(i, i + len);
                if(isPalindrome(substr)){
                    System.out.println(substr);
                    return;
                }
            }
        }
    }
    
    private static boolean isPalindrome(String str){
        int left = 0, right = str.length() - 1;
        while(left < right){
            if(str.charAt(left) != str.charAt(right))
                return false;
            left ++;
            right --;
        }
        return true;
    }
}

发表于 2021-04-11 21:52:05 回复(0)

C/C++

zzzhang2002

动态规划O(n²):

自底向上，最终的dp结果是上三角，保存当前位置的回文串，如果不是则为""；

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

int main(){
    string line;
    cin>>line;
    vector<vector<string>> dp(line.size()+1, vector<string>(line.size()+1, ""));

    for(int i=line.size(); i>0; i--){
        for(int j=i; j<=line.size(); j++){
            if(line[i-1] == line[j-1]) {
                if(j==i) {
                    dp[i][j] = line[i-1];
                } 
                else if( j==i+1 ){
                    dp[i][j] = line[i-1]+dp[i+1][j-1]+line[j-1];
                }
                else {
                    if(dp[i+1][j-1].size()!=0) { // 是回文
                        dp[i][j] = line[i-1] + dp[i+1][j-1] + line[j-1];
                    }
                }
            }
        }
    }
    // dp[i][j] => line_i  + line_sub[i+1,j-1] + line_j

    int maxlen = 0;
    string retstr = "";
    for(int i=1; i<=line.size(); i++){
        for(int j=1; j<=line.size(); j++){
            // cout<<dp[i][j]<<" ";
            if(dp[i][j].size()>maxlen){
                maxlen = dp[i][j].size();
                retstr = dp[i][j];
            }
        }
        // cout<<endl;
    }
    // cout<<maxlen<<endl;
    cout<<retstr<<endl;
    return 0;
}

暴力算法O(n³)：

#include <bits/stdc++.h> 
using namespace std;
bool ishw(string s){
    for(int i=0; i<=s.size()/2; i++){
        if(s[i]!=s[s.size()-1-i]){
            return false;
        }
    }
    return true;
}
int main() {
    string line;
    cin>>line;
    int n=line.size();
    // int ret = 0; 
    string ans = "";
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            string tmp = line.substr(i, j-i+1);
            if(ishw(tmp) && ans.size()<tmp.size()){
                ans = tmp;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

编辑于 2023-10-08 11:21:37 回复(0)

OfferOffer你要去哪里呀

枚举中心，注意0和n-1也要枚举，为了应付长度为1的字符串

#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
    cin >> s;
    int n = s.size();
    string ans;
    for (int i = 0; i < n; i++) {
        int j, k;
        for (j = i, k = i; j - 1 >= 0 && k + 1 < n && s[j - 1] == s[k + 1]; j--, k++){}
        if (ans.size() < k - j + 1) ans = s.substr(j, k - j + 1);
        for (j = i + 1, k = i; j - 1 >= 0 && k + 1 < n && s[j - 1] == s[k + 1]; j--, k++) {}
        if (ans.size() < k - j + 1) ans = s.substr(j, k - j + 1);
        //printf("%c %d %d\n", s[i], j, k);
    }
    cout << ans << endl;
    return 0;
}

发表于 2022-01-16 23:11:14 回复(0)

Python

maoxiaomao

s=input().strip()
t=[]
for i in range(len(s)):
    j=i-1
    k=i+1
    tmp=[]
    tmp.append(s[i])
    while j>=0 and k<len(s) and s[j]==s[k]: 
        tmp.insert(0,s[j])
        tmp.append(s[k])
        j=j-1
        k=k+1
    if len(tmp)>len(t):t=tmp
    j=i
    k=i+1
    tmp=[]    
    while j>=0 and k<len(s) and s[j]==s[k]:
        tmp.insert(0,s[j])
        tmp.append(s[k])
        j=j-1
        k=k+1
    if len(tmp)>len(t):t=tmp
tt=""
for i in range(len(t)):
    tt+=t[i]
print(tt)

发表于 2021-05-24 19:20:29 回复(0)

牛客12312341

有人暴力过了，算法笔试那么水的吗233

马拉车算法可以在O（n）解决该问题

我这里使用字符串hash+二分求出来的，时间复杂度O(NlogN)

#include<bits/stdc++.h>

using namespace std;

#define ull unsigned long long

const int N=1e5+100;

ull f1[N],f2[N];
ull p[N];

ull hash1(int l,int r){
    int len=r-l+1;
    return f1[r]-f1[l-1]*p[len];
}

ull hash2(int l,int r){
    int len=r-l+1;
    return f2[l]-f2[r+1]*p[len];
}

char ss[N];

int main(){
    cin>>ss+1;
    int n=strlen(ss+1);
    f1[0]=f2[n+1]=0,p[0]=1;
	for(int i=1;i<=n;i++){
		f1[i]=f1[i-1]*131+ss[i]-' '; 
		p[i]=p[i-1]*131;
	} 
	for(int i=n;i;i--){
		f2[i]=f2[i+1]*131+ss[i]-' ';
	}
    int ans=0,st;
    for(int i=1;i<=n;i++){
        int l=0,r=min(i,n-i),res;
        while(l<=r){
            int mid=(l+r)>>1;
            if(hash1(i-mid+1,i)==hash2(i+1,i+mid)) res=mid,l=mid+1;
            else r=mid-1;
        }
        if(2*res>ans){
            ans=2*res;
            st=i-res+1;
        }
        
        l=0,r=min(i-1,n-i);
        while(l<=r){
            int mid=(l+r)>>1;
            if(hash1(i-mid,i-1)==hash2(i+1,i+mid)) res=mid,l=mid+1;
            else r=mid-1;
        }
        if(2*res+1>ans){
            ans=2*res+1;
            st=i-res;
        }
        
    }
   // cout<<ans<<endl;
    for(int i=st;i<st+ans;i++) cout<<ss[i];
    return 0;
}

发表于 2021-05-12 00:23:12 回复(0)

牛客959758661号

一个个分析写了半天，还是穷举香

s1 = input()
t = ''
def hw(str1):
    if str1 == str1[::-1]:
        return True
    else:
        return False

for i in range(1,len(s1)+1):
    for j in range(len(s1)):
        s2 = s1[j:j+i]
        if hw(s2):
            if len(t) < len(s2):
                t = s2
print(t)

发表于 2021-04-20 16:46:45 回复(0)