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




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

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

我们可以使用它找到所有长度的回文。

示例:

word = abcdcbc

modifiedString = a#b#c#d#c#b#c

palinCount = 1010105010301

最长回文长度= 5;

最长回文= bcdcb

公共类MyLongestPalindrome {

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 : ");
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader bfr = new BufferedReader(isr);
    word = bfr.readLine();
    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;

    }

}

}

例如字符串“abaccddccefe”中的“ccddcc”

我想到了一个解决方案,但它运行在O(n ^ 2)时间

Algo 1:

步骤:它是一种强力方法

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

问题:1.这个算法运行在O(n ^ 2)时间。

Algo 2:

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

你们能想到一个在更好的时间运行的算法吗? 如果可能的话O(n)时间


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

并不是该字符串具有“ABC”和“CBA”作为其子字符串。 如果您反转原始字符串,它将是“ABCFEDCBA”。 最长的匹配子字符串是不是回文的“ABC”。

您可能需要另外检查此最长匹配子字符串是否实际上是一个运行时间为O(n ^ 3)的回文。


一个有效的Regexp解决方案,避免了暴力

从整个字符串长度开始,向下工作到2个字符,只要匹配成功就存在

对于"abaccddccefe" ,在返回ccddcc之前,正则表达式测试7匹配。

(。)()()()()()(\ 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

以下是javascript中的一个实现:

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');


嗨这是我的代码,找到字符串中最长的回文。 请参阅以下链接了解http://stevekrenzel.com/articles/longest-palnidrome算法

使用的测试数据是HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE

 //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;     
  }

对于线性解决方案,您可以使用Manacher算法。 还有另一个算法调用Gusfield算法,下面是java中的代码:

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();  
    }  
}  

你可以从我自己的博客中找到更多关于其他解决方案的信息,例如最佳O(n ^ 2)解决方案或Manacher算法。


就我所了解的问题而言,我们可以在中心索引周围找到回文,并在中心的左侧和右侧搜索我们的搜索。 考虑到并且知道输入的角落没有回文,我们可以将边界设置为1并且长度为1。 在注意字符串的最小和最大边界的同时,我们验证对称索引(右和左)位置处的字符对于每个中心位置是否相同,直到达到我们的最大上限中心。

外部循环是O(n)(最大n-2次迭代),内部while循环是O(n)(max(n / 2) - 1次迭代)

这是我的Java实现,使用其他用户提供的示例。

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 str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
        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
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321

我出于好奇,简单且不言自明的HTH编写了以下Java程序。 谢谢。

/**
 *
 * @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){
        String s="HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE";

        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;
}

试试字符串 - “HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE”; 它应该适用于偶数和奇数的朋友。 非常感谢Mohit!

使用namespace std;

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;
}

请参阅en.wikipedia.org/wiki/Longest_palindromic_substring有关此主题的en.wikipedia.org/wiki/Longest_palindromic_substring 。 来自以下文章的线性O(n)解决方案示例here Java实现:

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
{
    [self longestPalindrom:@"abcccbadeed"];
}

==输出===

输入:abcccde输出:ccc

输入:abcccbd输出:bcccb

输入:abedccde输出:edccde

输入:abcccdeed输出:契据

输入:abcccbadeed输出:abcccba


这是我的算法:

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

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

3)如果找到的回文大于前回文,则更新它

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

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

这在O(n)中运行。

希望能帮助到你。





palindrome