首页 > 试题广场 >

最长回文子串

[编程题]最长回文子串
  • 热度指数:179573 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的由小写字母构成的字符串 s,求出其最长回文子串的长度。

\hspace{15pt}子串为从原字符串中,连续的选择一段字符(可以全选、可以不选)得到的新字符串。
\hspace{15pt}一个字符串被称作回文串,当且仅当这个字符串从左往右读和从右往左读是相同的。

输入描述:
\hspace{15pt}在一行上输入一个长度为 1 \leqq {\rm len}(s) \leqq 350、仅由小写字母构成的字符串 s


输出描述:
\hspace{15pt}输出一个整数,表示字符串 s 的最长回文子串的长度。
示例1

输入

cdabbacc

输出

4

说明

\hspace{15pt}在这个样例中,\texttt{ 是最长的回文子串。
示例2

输入

a

输出

1
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
string findLongestPalindromeManacher(const string s){
    string s1("^#");
    for (auto ch : s){
        s1 += ch;
        s1 += '#';
    }
    s1 += '$';
    vector<int>pv(s1.length(), 0);//记录回文半径
    int index(0), mlen(1);
    for (int k1 = 2, mid = 1, mxr = 0; k1 < s1.length(); ++k1){
        pv[k1] = k1 < mxr ? min(pv[mid * 2 - k1], mxr - k1) : 1;
        while (s1[k1 + pv[k1]] == s1[k1 - pv[k1]]){
            ++pv[k1];//回文半径增加
        }
        if (mxr < mid + pv[k1]){
            mxr = mid + pv[k1];
            mid = k1;
        }
        if (mlen < pv[k1]){
            mlen = pv[k1];
            index = k1;
        }
    }
    return s.substr((index - mlen) / 2, mlen - 1);
}
int main(){
    string s;
    while (cin>>s)
    {
        string s1 = findLongestPalindromeManacher(s);
        cout << s1.length() << endl;
    }
    return 0;
}

发表于 2019-07-21 10:47:48 回复(3)
int main(){
    string str;
    while(cin >> str)
    {
        vector<vector<int>>dp(str.size(), vector<int>(str.size()));
        int ans = 1;
        for(int i = 0; i < str.size(); ++i)
        {
            dp[i][i] = 1;
            if(i < str.size() - 1)
            {
                if(str[i] == str[i+1])
                {
                    dp[i][i+1] = 1;
                    ans = 2;
                }
            }
        }
        
        for(int L = 3; L <= str.size(); ++L)
            for(int i = 0; i + L - 1 < str.size(); ++i)
            {
                int j = i + L -1;
                if(str[i] == str[j] && dp[i+1][j-1])
                {
                    dp[i][j] = 1;
                    ans = L;
                }
            }
        cout << ans << endl;
    }
}



虽然长点,但是简单粗暴......
发表于 2022-07-19 23:00:53 回复(0)
  function toManacherString(str) {
    let a = ['#'];
    for (let i=0;i<str.length;i++) {
      a.push(str[i]);
      a.push('#');
    }
    return a;
  }

  function manacher(str) {
    let a = toManacherString(str);
    let ra = Array(a.length).fill(0);
    let c = -1, r = -1;
    let max = Number.MIN_SAFE_INTEGER;
    debugger;
    for (let i = 0; i < a.length; i++) {
      if (r > i) {
        let pl = 2 * c - i;
        if (pl - ra[pl] > c - r) {
          ra[i] = ra[pl];
          continue;
        } else if (pl - ra[pl] < c - r) {
          ra[i] = r - i + 1;
          continue;
        } else {
          ra[i] = r - i + 1;
        }
      }
      while (i + ra[i] < ra.length && i - ra[i] > -1) {
        if (a[i + ra[i]] === a[i - ra[i]]) {
          ra[i]++;
        } else {
          break;
        }
      }
      if (i + ra[i] > r) {
        r = i + ra[i] - 1;
        c = i;
      }
      if (ra[i] > max) {
        max = ra[i];
      }
    }
    return max - 1;
  }
let input =readline();
print(manacher(input))


发表于 2022-07-02 16:37:25 回复(0)
数据规模不大,所以暴力解也行,直接由中心向两边扩展,全部遍历一遍。数据规模再大一点肯定就不行了。
时间复杂度O(N2),空间复杂度O(1),肯定不符合进阶要求了。
查资料Manacher算法能做到O(N)/O(N),不过看不懂,代码也长的多了
import java.util.Scanner;

public class Main{
    public static int lenRoundStr(String s, int left, int right){
        while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String inp = sc.nextLine();
        int maxlen = Integer.MIN_VALUE;
        for(int i=0; i<inp.length()-1; i++){
            int ans = Math.max(lenRoundStr(inp,i,i), lenRoundStr(inp,i,i+1));
            maxlen = Math.max(ans, maxlen);
        }
        System.out.println(maxlen);
    }
}


发表于 2022-04-22 11:39:43 回复(0)
import java.util.Scanner;
 
public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str = sc.nextLine();
            char [] arr = str.toCharArray();
            int count = 0;
            int len = str.length();
            for(int i=0; i<len; i++){
                int temp = len-1;
                int num = huiwen(arr,i,temp);
                count = num > count ? num :count;
            }
            System.out.println(count);
        }
    }
    public static int huiwen(char[] arr,int i, int temp){
        if(temp <= i){
            return 1;
        }else{
            int ttemp = 1;
            int n = (temp-i+1)/2;
            for(int j=0; j<n ;j++){
                if(!(arr[i+j] == arr[temp-j])){
                    int tnum = temp -1;
                    ttemp = huiwen(arr,i,tnum);
                    break;
                }else if( j == n-1){
                     ttemp = temp-i+1;
                }
            }
            return ttemp;
        }
    }
}
发表于 2022-02-21 12:18:19 回复(0)
8ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str=br.readLine())!=null){
            int len=str.length();
            int max=0;
            int temp;
            for(int i=0;i<len;i++){

                //去掉不需要的处理
                if(max%2==1){
                    if((len-i)<((max/2)+1)){
                        break;
                    }
                }else {
                    if((len-i)<(max/2)){
                        break;
                    }
                }

                temp=0;
                //奇数
                if(i+2<len && str.charAt(i)==str.charAt(i+2)){
                    temp++;
                    int left=i-1;
                    int right=i+3;
                    while (left>=0 && right<len) {
                        if(str.charAt(left)==str.charAt(right)){
                            temp++;
                            left--;
                            right++;
                        }else {
                            break;
                        }
                    }
                    max=Math.max(max,temp*2+1);
                }
                //偶数
                //必须对temp进行重置
                temp=0;
                if(i+1<len && str.charAt(i)==str.charAt(i+1)){
                    temp++;
                    int left=i-1;
                    int right=i+2;
                    while (left>=0 && right<len) {
                        if(str.charAt(left)==str.charAt(right)){
                            temp++;
                            left--;
                            right++;
                        }else {
                            break;
                        }
                    }
                    max=Math.max(max,temp*2);
                }

            }
            System.out.println(max);
        }

    }
}


发表于 2021-09-11 17:01:34 回复(0)
def longestPalindrome( s: str) -> str:
    if not s:
        return ""
    n = len(s)
    res=[]
    for i in range(1, n):
        # 中轴情况
        j = 1
        while i - j >= 0 and i + j <= n-1 and s[i - j] == s[i + j]:
            j += 1
        j-=1
        num=j*2+1
        res.append(num)
        # 对称情况
        j = 1
        while i - j >=0 and i + j - 1 <= n-1 and s[i - j] == s[i + j - 1]:
            j += 1
        j-=1
        num=j*2
        res.append(num)
    num=max(res)
    return num
while True:
    try:
        s=input()
        print(longestPalindrome(s))
    except:
        break

发表于 2021-08-17 16:05:32 回复(1)
//N为字符串长度,i为定位器,其作用是寻找最长回文子串的中心,left和right
//是从i左端(或自身)和右段延申出去的定位器,最终是最长回文字串左端减一和右端加一的位置。可以看到我把代码复制了两次,其中的不同就在于
//for循环中的left=i和left=i-1,这是因为最长回文字串有可能是偶数或者奇数个,此时i可能是X.5,或者X,(X为最长回文子串中心的位置)
//此外,本题如果出现了段越界,就是你先前定义的数组不够大的原因,一开始我定义了100个都不够用
#include <stdio.h>
#include <string.h>
int main( )
{
    char a[1000];
    int N=0,i=1,left,right,lenth;
    while(scanf("%s",a)!=EOF){
        //printf("%s",a);
        
    N=strlen(a);lenth=0;
        for(i=0;i<N;i++)
        {left=i,right=i+1;
    while(left>=0&&right<N&&a[left]==a[right])
    {
     left--;
     right++;
    }
    if(right-left-1>lenth)
    {
        lenth=right-left-1;
    }
        }
    for(i=0;i<N;i++)
        {left=i-1,right=i+1;
    while(left>=0&&right<N&&a[left]==a[right])
    {
     left--;
     right++;
    }
    if(right-left-1>lenth)
    {
        lenth=right-left-1;
    }
        }
printf("%d\n",lenth);
   }
        return 0;
}

发表于 2021-05-08 18:39:17 回复(0)
#include <iostream>
using namespace std;

int main() 
{
	
	string str;

	while ( cin >> str )
	{
		int len = str.size();
		bool dp[len][len];//字符串i到j区间是否为回文子串

		for (int i=0;i<len;i++)
		{
			for (int j=0;j<len;j++)
			{
				dp[i][j] = false;
			}
		}

		for (int i=0;i<len;i++)
		{
			dp[i][i] = true;
		}

		int imax=0;
		for (int j=1;j<len;j++)
		{
			for (int i=0;i<=j;i++)		
			{
				if (str[i] == str[j])
				{
					if (j-i<3)
					{
						dp[i][j] = true;
					}
					else
					{
						dp[i][j] = dp[i+1][j-1];
					}

					if (dp[i][j])
					{
						imax = imax > (j-i+1) ? imax : (j-i+1);
					}
				}
			}
		}

		cout << imax <<endl;

	}
	return 0;
}

发表于 2021-04-16 21:00:44 回复(0)
#include<stdio.h>
#include<string.h>
#define N 1024
 int main()
 {   char str[N];
  while (scanf("%s",str)!=EOF){
      int n= strlen(str);
      int i,k,sum,max;
      max=0;
      for (i=0;i<n;i++)
      {   sum=0;
          if(str[i]==str[i+1]) 
          { for(k=0;k<n;k++)
            {if(str[i-k]==str[i+k+1]) { sum=sum+1;  }
             else if(str[i-k]!=str[i+k]) break;}
          }
          if (max<sum) max=sum;
      }
      printf("%d",max*2);
 } return 0;
 }

发表于 2021-03-07 22:14:03 回复(0)
#include <stdio.h>

int main(void)
{
    char string[1000];
    int idx = 0;
    int right = 0;
    int left = 0;
    int cnt = 0;
    int maxCnt = 0;
    while (EOF != scanf("%s", string))
    {
        idx = 0;
        maxCnt = 0;
        cnt = 0;
        
        while (string[idx++] != '\0')
        {
            if (idx > 0 && string[idx] == string[idx - 1])
            {
                cnt = 2;
                left = idx - 1;
                right = idx;
            }
            else if (idx > 1 && string[idx] == string[idx - 2])
            {
                cnt = 3;
                left = idx - 2;
                right = idx;
            }
        
            while (left > 0 && 
                   string[right + 1] != '\0' &&
                   string[++right] == string[--left])
            {
                cnt += 2;
            }
        
            if (cnt > maxCnt) maxCnt = cnt;
            cnt = 0;
        }
        
        printf("%d\n", maxCnt);
    }
    
}
非常利于理解的解法
发表于 2021-03-03 22:06:55 回复(0)
  • just do it!~
#include <bits/stdc++.h>

using namespace std;

int checkSubstrValid(const string &input, int len, int left, int right) {
    bool isOdd = (left == right);
    int res;
    if (isOdd) {
        res = 1;
        --left;
        ++right;
    } else {
        res = 0;
    }
    for (; left >= 0 && right < len; --left, ++right) {
        if (input[left] == input[right]) {
            res += 2;
        } else {
            break;
        }
    }
    //cout << res << endl;
    return res;
}

int getMaxHuiwen(const string &input) {
    uint32_t n = input.length();
    if (n == 0 || n == 1) { return n; }
    int maxLen = 0;
    for (uint32_t i = 0; i < n-1; ++i) {
        maxLen = max(maxLen, checkSubstrValid(input, n, i, i));
        maxLen = max(maxLen, checkSubstrValid(input, n, i, i+1));
    }
    return maxLen;
}

int main () {
    string input;
    while (getline(cin, input)) {
        int res = getMaxHuiwen(input);
        if (res) { 
            cout << getMaxHuiwen(input) << endl;
        }
    }
    return 0;
}
发表于 2021-01-30 17:02:17 回复(0)
提供一种比较容易理解的思路, 我们判断回文一般比较容易理解的就是 从两头进行判断, 比如 str = abba, 令 l -> 1(a,索引位置), r -> 2(a, 索引位置), 首先判断 str[l] == str[r], 如果成立 则 l--, r++, 即 继续网两头比较。 这里考虑 可以以 l 和 r 都指向同一个位置开始, 奇数, l 和 r 指向相邻位,即上面的栗子那样, 偶数开始, 然后从头开始不断判断,找出最大长度。
代码如下:
//package june.code.byhehe.forOffer.HW;

import java.util.Scanner;

/**
 * 华为HJ85
 * 因为截获的串太长了,而且存在多种可能的情况(abaaab可看作是aba,或baaab的加密形式),Cathcer的工作量实在是太大了,他只能向电脑高手求助,你能帮Catcher找出最长的有效密码串吗?
 *
 * (注意:记得加上while处理多个测试用例)
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            String s = sc.nextLine().trim();
            // 以 i 和 i+1 为中心扩展
            String res="";
            for (int i = 0; i < s.length(); i++) {
                String s1 = getHuiWen(s, i, i);
                String s2 = getHuiWen(s, i, i+1);
                res = res.length()>s1.length()?res:s1;
                res = res.length()>s2.length()?res:s2;

            }
            System.out.println(res.length());
        }
    }

    public static String getHuiWen(String s, int l, int r){
        while (l>=0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        return (r-l) == 1?s.substring(l,r):s.substring(l+1, r);
    }
}


发表于 2020-08-18 09:35:23 回复(0)
package huaweitest;

import java.util.Scanner;

public class Main18 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            String s = cin.nextLine();
            int flag = 0, max = 0;
            //长度从最长开始
            for (int k = s.length(); k >= 1; k--) {
                int i = 0;
                //注意判断条件
                while (i + k <= s.length()) {
                    if (check(s.substring(i, i + k))) {
                        flag = 1;
                        max = k;
                        break;
                    }
                    i++;
                }
                if (flag == 1) {
                    break;
                }
            }
            System.out.println(max);
        }
    }

    public static boolean check(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

发表于 2020-08-15 20:45:42 回复(0)
while True:
    try:
        s = input()
        if(len(s)!=0):
            flag = False
            for i in range(len(s)+1)[::-1]:
                for j in range(len(s)+1-i):
                    temp = s[j:j+i]
                    if s[::-1].count(temp)>0 and temp==temp[::-1]:
                        print(len(temp))
                        flag = True
                        break
                if(flag):
                    break
    except:
        break
发表于 2020-07-11 15:36:57 回复(0)
while True:
    try:
        a = raw_input()
        m = len(a)
        dp = [[0]*m for _ in range(m)]
        ans = []
        for x in range(m):
            for y in range(m-x):
                i = y
                j = x + y
                if a[i] != a[j]:
                    dp[i][j] = 0
                else:
                    if j-i == 0:
                        dp[i][j] = 1
                    elif j-i == 1:
                        dp[i][j] = 2
                    else:
                        if dp[i+1][j-1] == 0:
                            dp[i][j] = 0
                        else:
                            dp[i][j] = dp[i+1][j-1] + 2
        for i in dp:
            ans.append(max(i))
        print max(ans)
    except:
        break
发表于 2019-07-16 15:09:48 回复(0)
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  string str;
  while(cin>>str){
    int len=0;
    int maxmum1=0;
    int maxmum2=0;
    for(int i=1;i<str.size()-2;i++){
         if(str[i]==str[i+1]){
           for(int j=i-1,m=i+2;j>=0,m<str.size();j--,m++){
           if(str[j]==str[m]){
              len=m-j+1;
              maxmum2=max(maxmum2,len);
             }
           else 
              break;
         }
    }
      else  if(str[i-1]==str[i+1]){
         for( int j=i-1;j>=0&&2*i-j<=str.size();j--){
         if(str[j]==str[i+i-j]){
           len=2*i-2*j+1;
           maxmum1=max(maxmum1,len);
         }
         else 
          break;
      } 
    }
    }
    maxmum1=max(maxmum1,maxmum2);
    cout<<maxmum1<<endl;
}
}
发表于 2019-06-21 16:37:31 回复(0)
马拉车
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int Manacher(string oriStr)
{
 string newStr;
 int len = oriStr.size();
 //插入间隔符
 for (int i = 0; i < len; i++)
 {
  newStr += '#';
  newStr += oriStr[i];
 }
 newStr += '#';
 len = 2 * len + 1;  //新串长度,必定为奇数
 int maxRight = 0;   //当前访问到的所有回文子串中,所能触及的最右一个字符的位置
 int pos = 0;        //maxRight对应的回文子串对称轴的位置
 int *RL = new int[len];
 int maxLength = 0;
 for (int i = 0; i < len; i++)
 {
  RL[i] = maxRight>i ? min(RL[2 * pos - i], maxRight - i) : 1;
  while (i - RL[i] >= 0 && RL[i] + i < len&&newStr[i - RL[i]] == newStr[i + RL[i]])
  {
   RL[i]++;    //以i为中心,在上步的基础上扩展,直至到达边界或左右字符不相等
  }

  if (maxRight < RL[i] + i)
  {
   maxRight = RL[i] + i;
   pos = i;
  }
  maxLength = max(maxLength, RL[i] - 1);
 }
 return maxLength;
}
int main()
{
 string str;
 while (cin >> str)
 {
  cout << Manacher(str) << endl;
 }
 return 0;
}

发表于 2018-05-28 20:56:41 回复(0)
// 分ABA, ABBA分别讨论,满足时,扩大到更大半径
#include <stdio.h>
#include <string.h>
int main () {
    char c[1000] = {0};    
    while (scanf("%s", c) != EOF) {
        int len = strlen(c);
        int fro = 0, beh = 0;
        int count_ABA = 0, count_ABA_max = 0;
        int count_ABBA = 0, count_ABBA_max = 0;
 
        for (int i = 0; i < len; i++) {
            fro = 1;
            beh = 0;
            count_ABBA = 0;
            while (c[i - beh] == c[i + fro] && (i - beh) >= 0
                  && (i + fro) < len){
                count_ABBA += 2;
                beh++;
                fro++;
            }    // 满足BB时,检验ABBA,CABBAC...
            
            if (count_ABBA_max < count_ABBA)
                count_ABBA_max = count_ABBA;
        }  // ABBA
        
        for (int i = 0; i < len; i++) {
            fro = 2;
            beh = 0;
            count_ABA = 1;
            while (c[i - beh] == c[i + fro] && (i - beh) >= 0
                  && (i + fro) < len){
                count_ABBA += 2;
                beh++;
                fro++;
            } // 满足B时,检验ABA,CABAC...

            
            if (count_ABA_max < count_ABA)
                count_ABA_max = count_ABA;
        }  // ABA,包括B
        
        if (count_ABBA_max < count_ABA_max)
            count_ABBA_max = count_ABA_max;
        
        printf("%d\n", count_ABBA_max);
    }
    
    return 0;
}

编辑于 2017-08-29 17:21:25 回复(1)
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    while(cin>>s)
    {
        int i,j,k1,k2,max=0;
        int len=s.size();
        
        for(i=0;i<len-1;i++)
            for(j=i+1;j<len;j++)
                if(s[i]==s[j])
                {
                    for(k1=i+1,k2=j-1;k1<=k2;k1++,k2--)
                        if(s[k1]!=s[k2])
                             break;
                    if(k1>k2)
                        if(j-i+1>max)
                          max=j-i+1;
                }
         cout<<max<<endl;        
            
    }
}
发表于 2017-06-28 19:51:29 回复(0)