给定一个字符串str, 返回str中最长回文子串的长度
[举例]
str=“123”。其中的最长回文子串“1”或者“2”或者“3”,所以返回1。
str=“abc1234321ab”。其中的最长回文子串“1234321”,所以返回7。
[要求] 如果str的长度为N,解决原问题的时间复杂度都达到O(N).
输入为一个字符串str
输出一个整数表示最长回文子串的长度
123
1
abc1234321ab
7
设N表示输入字符串的长度保证输入字符中只含有小写字母及数字
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 s = br.readLine(); char[] str = preprocessing(s.toCharArray()); // 预处理原始字符串,往每个字符之间加# int[] radius = new int[str.length]; int R = -1, C = -1; // 最远右边界(下一位置)及其对应的中心位置 int max = 1; for(int i = 0; i < str.length; i++){ radius[i] = i < R? Math.min(radius[2*C - i], R - i): 1; // i在R内部或不在R内部的情况下,不需要检查的范围 while(i + radius[i] < str.length && i - radius[i] >= 0){ // 没有越界 if(str[i + radius[i]] == str[i - radius[i]]){ // 往外扩成功了半径就增加 radius[i] ++; }else{ break; } } // 最远右边界变大时要更新其位置和中心 if(i + radius[i] > R){ R = i + radius[i]; C = i; } max = Math.max(max, radius[i]); } System.out.println(max - 1); } private static char[] preprocessing(char[] str) { StringBuilder sb = new StringBuilder(); for(char c: str) sb.append("#").append(c); sb.append("#"); return sb.toString().toCharArray(); } }
def Manacher(long_str): # 插入特殊字符# long_str_list = list(long_str) long_str = '#' + '#'.join(long_str_list) + '#' len_long_str = len(long_str) R = -1 C = -1 _max_radius = 1 _max_C = 0 radius = [0] * len_long_str for idx in range(len(long_str)): radius[idx] = max(min(radius[2 * C - idx], R - idx), 1) if idx < R else 1 while(idx + radius[idx] < len_long_str and idx - radius[idx] >= 0): if (long_str[idx + radius[idx]] == long_str[idx - radius[idx]]): radius[idx] += 1 else: break if idx + radius[idx] > R: R = idx + radius[idx] C = idx if _max_radius < radius[idx]: _max_radius = radius[idx] _max_C = idx return long_str[_max_C - _max_radius + 1: _max_C + _max_radius].replace('#','') password = input() print(len(Manacher(password)))
import java.util.*; public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); char[] mArr = getMArr(s); System.out.println(Manacher(mArr)); } public static char[] getMArr(String s) { char[] str = s.toCharArray(); char[] res = new char[2*str.length+1]; for (int i = 0; i < res.length; i++) { if (i % 2 == 0) { res[i] = '#'; } else { res[i] = str[i/2]; } } return res; } public static int Manacher(char[] str) { //记录回文子串的半径的数组 int[] pArr = new int[str.length]; //记录回文结构可以到达的最右index的下一位置 int R = -1; //记录最大回文结构的中心 int c = -1; int max = Integer.MIN_VALUE; for (int i = 0; i < str.length; i++) { //设置初始回文结构,此情况下为i'回文范围要么在L~R内部,要么超出L pArr[i] = R > i ? Math.min(R-i, pArr[2*c-i]) : 1; //当以i为中心检测的回文范围没有超出整个数组时 while (i + pArr[i] < str.length && i - pArr[i] > -1) { //对应此时的i在R外或者i'回文范围正好落在L上 if (str[i + pArr[i]] == str[i - pArr[i]]) //因为记录的是半径长度,只需要+1即可 pArr[i]++; else //若已经实现最大回文结构,则根本不会更新 break; } //更新相关信息 if(i + pArr[i] > R) { R = i + pArr[i]; c = i; } max = Math.max(max, pArr[i]); } return max - 1; } }
#include<cstdio> (802)#include<cstring> bool ishuiwen(char str[],int l,int r){ int k=0; for(int i=l;i<=(l+r)/2;i++){ if(str[i]!=str[r-k]) return false; k++; } return true; } int main(){ char str[500010]; int maxlen; while(scanf("%s",str)!=EOF){ int len=strlen(str); maxlen=1; for(int i=0;i<len-maxlen;++i){ for(int j=i+maxlen;j<len;++j){ if(ishuiwen(str,i,j)) { maxlen=j-i+1; } } } printf("%d\n",maxlen); } return 0; }