Escreva uma função que retorne o palíndromo mais longo em uma determinada string

por exemplo, "ccddcc" na string "abaccddccefe"

Pensei em uma solução, mas ela funciona em tempo O (n ^ 2)

Algo 1:

Passos: é um método de força bruta

1. Tenha 2 loops
   for para i = 1 a i menor que array.length -1
   para j = i + 1 a j menor que array.length
2. Desta forma, você pode obter substring de todas as combinações possíveis do array
3. Possui uma função de palíndromo que verifica se uma string é palíndromo
4. então para cada substring (i, j) chame esta função, se for um palíndromo armazene-a em uma variável de string
5. Se você encontrar a próxima substring de palíndromo e se ela for maior que a atual, substitua-a pela atual.
6. Finalmente sua variável de string terá a resposta

Problemas: 1. Este algo é executado em tempo O (n ^ 2).

Algo 2:

1. Inverta a string e armazene-a em uma matriz diferente
2. Agora encontre a maior substring correspondente entre ambas as matrizes
3. Mas isso também é executado no tempo O (n ^ 2)

Vocês podem pensar em um algo que funciona em um momento melhor. Se possível, tempo O (n)

Você pode encontrar o palíndromo mais longo usando o algoritmo de Manacher no O(n)tempo! Sua implementação pode ser encontrada aqui e aqui .

Para entrada String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE", encontra a saída correta, que é 1234567887654321.

O Algo 2 pode não funcionar para todas as cordas. Aqui está um exemplo de tal string "ABCDEFCBA".

Não que a string tenha "ABC" e "CBA" como substring. Se você inverter a string original, será "ABCFEDCBA". e a substring correspondente mais longa é "ABC", que não é um palíndromo.

Você pode precisar verificar adicionalmente se esta substring correspondente mais longa é na verdade um palíndromo que tem o tempo de execução de O (n ^ 3).

Pelo que entendi o problema, podemos encontrar palíndromos em torno de um índice central e abranger nossa pesquisa nos dois sentidos, à direita e à esquerda do centro. Dado isso e sabendo que não há palíndromo nos cantos da entrada, podemos definir os limites para 1 e comprimento-1. Prestando atenção aos limites mínimo e máximo da String, verificamos se os caracteres nas posições dos índices simétricos (direita e esquerda) são os mesmos para cada posição central até chegarmos ao centro do limite superior máximo.

O loop externo é O (n) (max n-2 iterações), e o loop while interno é O (n) (max ao redor (n / 2) - 1 iterações)

Aqui está minha implementação Java usando o exemplo fornecido por outros usuários.

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

O resultado disso é o seguinte:

marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321

com regex e ruby, você pode escanear palíndromos curtos como este:

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

Eu escrevi o seguinte programa Java por curiosidade, HTH simples e autoexplicativo. Obrigado.

/**
 *
 * @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);
    }
}

Esta pergunta me foi feita recentemente. Aqui está a solução que eu [eventualmente] encontrei. Fiz isso em JavaScript porque é muito simples nessa linguagem.

O conceito básico é que você percorre a linha procurando o menor palíndromo de vários caracteres possível (seja um de dois ou três caracteres). Depois de fazer isso, expanda as bordas em ambos os lados até que deixe de ser um palíndromo. Se esse comprimento for maior do que o atual, armazene-o e siga em frente.

// This does the expanding bit.
function getsize(s, start, end) {
    var count = 0, i, j;
    for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
        if (s[i] !== s[j]) {
            return count;
        }
        count = j - i + 1; // keeps track of how big the palindrome is
    }
    return count;
}

function getBiggestPalindrome(s) {
    // test for simple cases
    if (s === null || s === '') { return 0; }
    if (s.length === 1) { return 1; }
    var longest = 1;
    for (var i = 0; i < s.length - 1; i++) {
        var c = s[i]; // the current letter
        var l; // length of the palindrome
        if (s[i] === s[i+1]) { // this is a 2 letter palindrome
            l = getsize(s, i, i+1);
        }
        if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
            l = getsize(s, i+1, i+1);
        }
        if (l > longest) { longest = l; }
    }
    return longest;
}

Isso definitivamente poderia ser limpo e otimizado um pouco mais, mas deve ter um desempenho muito bom em todos, exceto no pior cenário (uma string da mesma letra).

Olá, aqui está o meu código para encontrar o palíndromo mais longo da string. Consulte o seguinte link para compreender o algoritmo http://stevekrenzel.com/articles/longest-palnidrome

Os dados de teste usados ​​são 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;     
  }

Veja o artigo da Wikipedia sobre este tópico. Exemplo de implementação do algoritmo de Manacher Java para solução linear O (n) do artigo abaixo:

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

Isso retornará a string mais longa do palíndromo de uma determinada string

-(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"];
}

== SAÍDA ===

Entrada: abcccde Saída: ccc

Entrada: abcccbd Saída: bcccb

Entrada: abedccde Saída: edccde

Entrada: abcccdeed Saída: escritura

Entrada: abcccbadeed Saída: abcccba

Aqui está uma implementação em 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');

Para solução linear, você pode usar o algoritmo de Manacher. Existe outro algoritmo chamado Algoritmo de Gusfield, e abaixo está o código em 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();  
    }  
}  

Você pode encontrar mais sobre outras soluções, como a melhor solução O (n ^ 2) ou algoritmo de Manacher em meu próprio blog .

Aqui eu escrevi uma lógica, experimente :)

public class palindromeClass{

public  static String longestPalindromeString(String in) {
        char[] input = in.toCharArray();
        int longestPalindromeStart = 0;
        int longestPalindromeEnd = 0;

        for (int mid = 0; mid < input.length; mid++) {
            // for odd palindrome case like 14341, 3 will be the mid
            int left = mid-1;
            int right = mid+1;
            // we need to move in the left and right side by 1 place till they reach the end
            while (left >= 0 && right < input.length) {
                // below check to find out if its a palindrome
                if (input[left] == input[right]) {
                    // update global indexes only if this is the longest one till now
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                else
                    break;
                left--;
                right++;
            }
            // for even palindrome, we need to have similar logic with mid size 2
            // for that we will start right from one extra place
            left = mid;
            right = mid + 1;// for example 12333321 when we choose 33 as mid
            while (left >= 0 && right < input.length)
            {
                if (input[left] == input[right]) {
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                else
                    break;
                left--;
                right++;
            }


        }
        // we have the start and end indexes for longest palindrome now
        return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
    }
public static void main(String args[]){
System.out.println(longestPalindromeString("HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE"));
}

}

Esta solução é de complexidade O (n ^ 2). O (1) é a complexidade do espaço.

public class longestPalindromeInAString {

        public static void main(String[] args) {
            String a =  "xyMADAMpRACECARwl"; 
            String res = "";
            //String longest = a.substring(0,1);
            //System.out.println("longest => " +longest);
            for (int i = 0; i < a.length(); i++) {
                String temp = helper(a,i,i);//even palindrome
                if(temp.length() > res.length()) {res = temp ;}
                temp = helper(a,i,i+1);// odd length palindrome
                if(temp.length() > res.length()) { res = temp ;}

            }//for
            System.out.println(res);
            System.out.println("length of " + res + " is " + res.length());

        }

        private static String helper(String a, int left, int right) {
            while(left>= 0 && right <= a.length() -1  &&  a.charAt(left) == a.charAt(right)) {
                left-- ;right++ ;
            }
            String curr = a.substring(left + 1 , right);
            System.out.println("curr =>" +curr);
            return curr ;
        }

    }

#longest palindrome
s='HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE'
out1=[]
def substring(x):
    for i in range(len(x)):
        a=x[i:]
        b=x[:-i]
        out1.append(a)
        out1.append(b)
        
    return out1

for i in range(len(s)):
    substring(s[i:])    
final=set([item for item in out1 if len(item)>2])
final
palind={item:len(item) for item in final if item==item[::-1]}
print(palind)
sorted(palind.items(),reverse=True, key=lambda x: x[1])[0]

{'DED': 3, '123456789987654321': 18, '67899876': 8, 'ABCDEDCBA': 9, '456789987654': 12, '34567899876543': 14, 'BCDEDCB': 7, 'ABA': 3, ' 5678998765 ': 10,' 2345678998765432 ': 16,' CDEDC ': 5,' 789987 ': 6,' 8998 ': 4} (' 123456789987654321 ', 18)

Aqui está meu algoritmo:

1) definir o centro atual para ser a primeira letra

2) expandir simultaneamente para a esquerda e para a direita até encontrar o palíndromo máximo em torno do centro atual

3) se o palíndromo que você encontrar for maior do que o palíndromo anterior, atualize-o

4) definir o centro atual como a próxima letra

5) repita os passos 2) a 4) para todas as letras da string

Isso é executado em O (n).

Espero que ajude.

Referência: Wikipedia.com

O melhor algoritmo que já encontrei, com complexidade O (N)

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

minha solução é:

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