# algorithm - 最长回文子串递归 - 给定一个字符串s找到s中最长的回文子串你可以假设s的最大长度为1000

## 编写一个返回给定字符串中最长回文的函数 (14)

1. 修改字符串以使用分隔符分隔每个字符[这是包含奇数和偶数回文]
2. 找到每个角色周围的回文，将其视为中心

word = abcdcbc

modifiedString = a＃b＃c＃d＃c＃b＃c

palinCount = 1010105010301

``````static String word;
static int wordlength;
static int highestcount = 0;
static int newlength;
static char[] modifiedString; // stores modified string
static int[] palinCount; // stores palindrome length at each position
static char pound = '#';

public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
System.out.println("Enter String : ");
wordlength = word.length();
newlength = (wordlength * 2) - 1;
convert();
findpalindrome();
display();
}

// Inserting # in string
public static void convert() {

modifiedString = new char[newlength];
int j = 0;
int i;
for (i = 0; i < wordlength - 1; i++) {
modifiedString[j++] = word.charAt(i);
modifiedString[j++] = pound;
}
modifiedString[j] = word.charAt(i);
}

// display all palindromes of highest length
public static void display() {
String palindrome;
String s = new String(modifiedString);
System.out.println("Length of longest palindrome = " + highestcount);
for (int i = 0; i < newlength; i++) {
if (palinCount[i] == highestcount) {
palindrome = s.substring(i - (highestcount - 1), i
+ (highestcount));
i = i + (highestcount - 1);
palindrome = palindrome.replace("#", "");
System.out.println(palindrome);
}
}
}

// populate palinCount with length of palindrome string at each position
public static void findpalindrome() {
int left, right, count;
palinCount = new int[newlength];
palinCount[0] = 1;
palinCount[newlength - 1] = 1;
for (int i = 1; i < newlength - 1; i++) {
count = 0;
left = i - 1;
right = i + 1;
;
if (modifiedString[i] != pound)
count++;
while (left >= 0 && right < newlength) {
if (modifiedString[left] == modifiedString[right]) {
if (modifiedString[left] != pound)
count = count + 2;
left--;
right++;
} else
break;
}

palinCount[i] = count;
highestcount = count > highestcount ? count : highestcount;

}

}
``````

}

Algo 1：

1. 有2个for循环
对于i = 1到i小于array.length -1
对于j = i + 1到j小于array.length
2. 这样你就可以得到数组中每个可能组合的子串
3. 有一个回文函数来检查一个字符串是否是回文
4. 所以对于每个子字符串（i，j）调用该函数，如果它是一个回文存储在一个字符串变量中
5. 如果您找到下一个回文子字符串，并且如果它大于当前字符串，请将其替换为当前字符串。
6. 最后你的字符串变量会有答案

Algo 2：

1. 反转字符串并将其存储在不同的数组中
2. 现在找到两个数组之间最大的匹配子字符串
3. 但是这也在O（n ^ 2）时间内运行

Algo 2可能不适用于所有字符串。 这是一个这样的字符串“ABCDEFCBA”的例子。

（。）（）（）（）（）（）（\ 6）（\ 5）（\ 4）（\ 3）（\ 2）（\ 1）
（。）（）（）（）（）（）（\ 5）（\ 4）（\ 3）（\ 2）（\ 1）
（。）（）（）（）（）（\ 5）（\ 4）（\ 3）（\ 2）（\ 1）
（。）（）（）（）（）（\ 4）（\ 3）（\ 2）（\ 1）
（。）（）（）（）（\ 4）（\ 3）（\ 2）（\ 1）
（。）（）（）（）（\ 3）（\ 2）（\ 1）
（。）（）（）（\ 3）（\ 2）（\ 1）

vbs

``````Dim strTest
wscript.echo Palindrome("abaccddccefe")
``````

vba

``````Sub Test()
Dim strTest
MsgBox Palindrome("abaccddccefe")
End Sub
``````

``````Function Palindrome(strIn)

Set objRegex = CreateObject("vbscript.regexp")

For lngCnt1 = Len(strIn) To 2 Step -1
lngCnt = lngCnt1 \ 2
strPal = vbNullString

For lngCnt2 = lngCnt To 1 Step -1
strPal = strPal & "(\" & lngCnt2 & ")"
Next

If lngCnt1 Mod 2 = 1 Then strPal = "(.)" & strPal

With objRegex
.Pattern = Replace(Space(lngCnt), Chr(32), "(.)") & strPal
If .Test(strIn) Then
Palindrome = .Execute(strIn)(0)
Exit For
End If
End With
Next

End Function
``````

``````PROMPT> irb
>> s = "longtextwithranynarpalindrome"
=> "longtextwithranynarpalindrome"
>> s =~ /((\w)(\w)(\w)(\w)(\w)\6\5\4\3\2)/; p \$1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\w\5\4\3\2)/; p \$1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\5\4\3\2)/; p \$1
nil
=> nil
>> s =~ /((\w)(\w)(\w)\w\4\3\2)/; p \$1
"ranynar"
=> nil
``````

``````var longestPalindromeLength = 0;
var longestPalindrome = ''

function isThisAPalidrome(word){
var reverse = word.split('').reverse().join('')
return word == reverse
}

function findTheLongest(word){ // takes a word of your choice
for(var i = 0; i < word.length; i++){ // iterates over each character
var wordMinusOneFromBeginning = word.substr(i, word.length) // for each letter, create the word minus the first char
for(var j = wordMinusOneFromBeginning.length; j > 0; j--){ // for the length of the word minus the first char
var wordMinusOneFromEnding = wordMinusOneFromBeginning.substr(0, j) // create a word minus the end character
if(wordMinusOneFromEnding <= 0) // make sure the value is more that 0,
continue // if more than zero, proced to next if statement
if(isThisAPalidrome(wordMinusOneFromEnding)){ // check if the word minus the first character, minus the last character = a plaindorme
if(wordMinusOneFromEnding.length > longestPalindromeLength){ // if it is
longestPalindromeLength = wordMinusOneFromEnding.length; // save its length
longestPalindrome = wordMinusOneFromEnding // and save the string itself
} // exit the statement that updates the longest palidrome
} // exit the stament that checks for a palidrome
} // exit the loop that goes backwards and takes a letter off the ending
} // exit the loop that goes forward and takes off the beginning letter
return console.log('heres the longest string: ' + longestPalindrome
+ ' its ' + longestPalindromeLength + ' charachters in length'); // return the longest palidrome! :)
}
findTheLongest('bananas');``````

`````` //Function GetPalindromeString

public static string GetPalindromeString(string theInputString)
{

int j = 0;
int k = 0;
string aPalindrome = string.Empty;
string aLongestPalindrome = string.Empty ;
for (int i = 1; i < theInputString.Length; i++)
{
k = i + 1;
j = i - 1;
while (j >= 0 && k < theInputString.Length)
{
if (theInputString[j] != theInputString[k])
{
break;
}
else
{
j--;
k++;
}
aPalindrome = theInputString.Substring(j + 1, k - j - 1);
if (aPalindrome.Length > aLongestPalindrome.Length)
{
aLongestPalindrome = aPalindrome;
}
}
}
return aLongestPalindrome;
}
``````

``````public class Solution {
char[] temp;
public int match(int a, int b,int len){
int i = 0;
while (a-i>=0 && b+i<len && temp[a-i] == temp[b+i]) i++;
return i;
}

public String longestPalindrome(String s) {

//This makes use of the assumption that the string has not more than 1000 characters.
temp=new char[1001*2];
int[] z=new int[1001 * 2];
int L=0, R=0;
int len=s.length();

for(int i=0;i<len*2+1;i++){
temp[i]='.';
}

for(int i=0;i<len;++i){
temp[i*2+1] = s.charAt(i);
}

z[0]=1;
len=len*2+1;

for(int i=0;i<len;i++){
int ii = L - (i - L);
int n = R + 1 - i;
if (i > R)
{
z[i] = match(i, i,len);
L = i;
R = i + z[i] - 1;
}
else if (z[ii] == n)
{
z[i] = n + match(i-n, i+n,len);
L = i;
R = i + z[i] - 1;
}
else
{
z[i] = (z[ii]<= n)? z[ii]:n;
}
}

int n = 0, p = 0;
for (int i=0; i<len; ++i)
if (z[i] > n)
n = z[p = i];

StringBuilder result=new StringBuilder();
for (int i=p-z[p]+1; i<=p+z[p]-1; ++i)
if(temp[i]!='.')
result.append(String.valueOf(temp[i]));

return result.toString();
}
}
``````

``````class LongestPalindrome {

/**
* @param input is a String input
* @return The longest palindrome found in the given input.
*/
public static String getLongestPalindrome(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1;  rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
leftIndex--;  rightIndex++;
}
}
return longestPalindrome;
}

public static void main(String ... args) {
String longestPali = getLongestPalindrome(str);
System.out.println("String: " + str);
System.out.println("Longest Palindrome: " + longestPali);
}
}
``````

``````marcello:datastructures marcello\$ javac LongestPalindrome
marcello:datastructures marcello\$ java LongestPalindrome
Longest Palindrome: 12345678987654321
``````

``````/**
*
* @author sanhn
*/
public class CheckPalindrome {

private static String max_string = "";

public static void checkSubString(String s){
System.out.println("Got string is "+s);
for(int i=1;i<=s.length();i++){
StringBuilder s1 = new StringBuilder(s.substring(0,i));
StringBuilder s2 = new StringBuilder(s.substring(0,i));
s2.reverse();
if(s1.toString().equals(s2.toString())){
if(max_string.length()<=s1.length()){
max_string = s1.toString();
System.out.println("tmp max is "+max_string);
}

}
}
}

public static void main(String[] args){

for(int i=0; i<s.length(); i++)
checkSubString(s.substring(i, s.length()));

System.out.println("Max string is "+max_string);
}
}
``````

``````static string GetPolyndrom(string str)
{
string Longest = "";

for (int i = 0; i < str.Length; i++)
{
if ((str.Length - 1 - i) < Longest.Length)
{
break;
}
for (int j = str.Length - 1; j > i; j--)
{
string str2 = str.Substring(i, j - i + 1);
if (str2.Length > Longest.Length)
{
if (str2 == str2.Reverse())
{
Longest = str2;
}
}
else
{
break;
}
}

}
return Longest;
}
``````

``````string largestPal(string input_str)
{
string isPal = "";
string largest = "";
int j, k;
for(int i = 0; i < input_str.length() - 1; ++i)
{
k = i + 1;
j = i - 1;

// starting a new interation
// check to see if even pal
if(j >= 0 && k < input_str.length()) {
if(input_str[i] == input_str[j])
j--;
else if(input_str[i] == input_str[j]) {
k++;
}
}
while(j >= 0 && k < input_str.length())
{
if(input_str[j] != input_str[k])
break;
else
{
j--;
k++;
}
isPal = input_str.substr(j + 1, k - j - 1);
if(isPal.length() > largest.length()) {
largest = isPal;
}
}
}
return largest;
}
``````

import java.util.Arrays; public class ManachersAlgorithm {public static String findLongestPalindrome（String s）{if（s == null || s.length（）== 0）return“”;

``````char[] s2 = addBoundaries(s.toCharArray());
int[] p = new int[s2.length];
int c = 0, r = 0; // Here the first element in s2 has been processed.
int m = 0, n = 0; // The walking indices to compare if two elements are the same
for (int i = 1; i<s2.length; i++) {
if (i>r) {
p[i] = 0; m = i-1; n = i+1;
} else {
int i2 = c*2-i;
if (p[i2]<(r-i)) {
p[i] = p[i2];
m = -1; // This signals bypassing the while loop below.
} else {
p[i] = r-i;
n = r+1; m = i*2-n;
}
}
while (m>=0 && n<s2.length && s2[m]==s2[n]) {
p[i]++; m--; n++;
}
if ((i+p[i])>r) {
c = i; r = i+p[i];
}
}
int len = 0; c = 0;
for (int i = 1; i<s2.length; i++) {
if (len<p[i]) {
len = p[i]; c = i;
}
}
char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
return String.valueOf(removeBoundaries(ss));   }
private static char[] addBoundaries(char[] cs) {
if (cs==null || cs.length==0)
return "||".toCharArray();

char[] cs2 = new char[cs.length*2+1];
for (int i = 0; i<(cs2.length-1); i = i+2) {
cs2[i] = '|';
cs2[i+1] = cs[i/2];
}
cs2[cs2.length-1] = '|';
return cs2;   }
private static char[] removeBoundaries(char[] cs) {
if (cs==null || cs.length<3)
return "".toCharArray();

char[] cs2 = new char[(cs.length-1)/2];
for (int i = 0; i<cs2.length; i++) {
cs2[i] = cs[i*2+1];
}
return cs2;   }     }
``````

``````-(BOOL)isPalindromString:(NSString *)strInput
{
if(strInput.length<=1){
return NO;
}
int halfLenth = (int)strInput.length/2;

BOOL isPalindrom = YES;
for(NSInteger i=0; i<halfLenth; i++){

char a = [strInput characterAtIndex:i];
char b = [strInput characterAtIndex:(strInput.length-1)-i];

if(a != b){
isPalindrom = NO;
break;
}
}
NSLog(@"-%@- IS Plaindrom %@",strInput,(isPalindrom ? @"YES" : @"NO"));
return isPalindrom;
}

-(NSString *)longestPalindrom:(NSString *)strInput
{
if(strInput.length<=1){
return @"";
}

NSString *strMaxPalindrom = @"";

for(int i = 0; i<strInput.length ; i++){

for(int j = i; j<strInput.length ; j++){

NSString *strSub = [strInput substringWithRange:NSMakeRange(i, strInput.length-j)];

if([self isPalindromString:strSub]){

if(strSub.length>strMaxPalindrom.length){

strMaxPalindrom = strSub;
}
}
}
}
NSLog(@"-Max - %@",strMaxPalindrom);
return strMaxPalindrom;
}

-(void)test
{
}
``````

==输出===

1）将当前中心设置为第一个字母

2）同时向左和向右扩展，直到找到当前中心周围的最大回文数

3）如果找到的回文大于前回文，则更新它

4）将当前中心设置为下一个字母

5）对字符串中的所有字母重复步骤2）至4）