algorithm - saber - Escribe una función que devuelve el palíndromo más largo en una cadena dada

palindromo recursivo en c

Question

por ejemplo, "ccddcc" en la cadena "abaccddccefe"

Pensé en una solución pero funciona en O (n ^ 2) vez

Algo 1:

Pasos: es un método de fuerza bruta

1. Tener 2 para bucles
   para i = 1 ai menos que array.length -1
   para j = i + 1 a j menos que array.length
2. De esta forma puede obtener una subcadena de todas las combinaciones posibles de la matriz
3. Tiene una función de palíndromo que comprueba si una cadena es palíndromo
4. entonces para cada subcadena (i, j) llame a esta función, si es un palíndromo almacénelo en una variable de cadena
5. Si encuentra la siguiente subcadena palindrómica y si es mayor que la actual, reemplácela por la actual.
6. Finalmente, su variable de cadena tendrá la respuesta

Problemas: 1. Este algo se ejecuta en O (n ^ 2) tiempo.

Algo 2:

1. Invierta el hilo y guárdelo en una matriz diferente
2. Ahora encuentre la subcadena de mayor coincidencia entre ambas la matriz
3. Pero esto también se ejecuta en O (n ^ 2) tiempo

¿Pueden pensar en algo que funcione en un mejor momento? Si es posible O (n) tiempo

Answer 1

1. Modifique la cadena para separar cada carácter usando un separador [esto es para incorporar los palíndromos impares y pares]
2. Encuentra palíndromos alrededor de cada personaje que lo trata como un centro

Podemos encontrar todos los palíndromos de toda longitud usando esto.

Muestra:

palabra = abcdcbc

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

palinCount = 1010105010301

longitud del palíndromo más largo = 5;

palindrome más largo = bcdcb

clase pública 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;

    }

}

}

Answer 2

¡Puedes encontrar el palíndromo más largo usando en.wikipedia.org/wiki/Longest_palindromic_substring en el tiempo O(n) ! Su implementación se puede encontrar here y here .

Para String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" entrada String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" encuentra la salida correcta que es 1234567887654321 .

Answer 3

Aquí está mi algoritmo:

1) establecer el centro actual para ser la primera letra

2) expandir simultáneamente hacia la izquierda y hacia la derecha hasta que encuentre el palíndromo máximo alrededor del centro actual

3) si el palíndromo que encuentras es más grande que el palíndromo anterior, actualízalo

4) establecer el centro actual para ser la siguiente letra

5) repita los pasos 2) a 4) para todas las letras de la cadena

Esto se ejecuta en O (n).

Espero eso ayude.

Answer 4

Aquí hay una implementación en 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'');

Answer 5

Aquí he escrito una lógica, pruébalo :)

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

}

Answer 6

El Algo 2 puede no funcionar para todas las cuerdas. Aquí hay un ejemplo de una cadena de este tipo "ABCDEFCBA".

No es que la cadena tenga "ABC" y "CBA" como su subcadena. Si invierte la cadena original, será "ABCFEDCBA". y la subcadena de mayor coincidencia es "ABC", que no es un palíndromo.

Es posible que deba verificar adicionalmente si esta subcadena de mayor coincidencia es en realidad un palíndromo que tiene el tiempo de ejecución de O (n ^ 3).

Answer 7

El siguiente código calcula Palidrom para cadenas de longitud y longitud impar.

No es la mejor solución pero funciona para ambos casos

HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE

private static String getLongestPalindrome(String string) {
    String odd = getLongestPalindromeOdd(string);
    String even = getLongestPalindromeEven(string);
    return (odd.length() > even.length() ? odd : even);
}

public static String getLongestPalindromeOdd(final String input) {
    int rightIndex = 0, leftIndex = 0;
    String currentPalindrome = "", longestPalindrome = "";
    for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
        leftIndex = centerIndex;
        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 String getLongestPalindromeEven(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;
}

Answer 8

Esta solución tiene una complejidad O (n ^ 2). O (1) es la complejidad del espacio.

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

    }

Answer 9

Esto devolverá la cadena palindrome más larga de una cadena dada

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

== SALIDA ===

Entrada: abcccde Salida: ccc

Entrada: abcccbd Salida: bcccb

Entrada: abedccde Salida: edccde

Entrada: abcccdeed Salida: escritura

Entrada: abcccbadeed Salida: abcccba

Answer 10

Hasta donde he entendido el problema, podemos encontrar palíndromos alrededor de un índice central y abarcar nuestra búsqueda en ambos sentidos, a la derecha e izquierda del centro. Dado eso y sabiendo que no hay palíndromo en las esquinas de la entrada, podemos establecer los límites en 1 y longitud-1. Mientras prestamos atención a los límites mínimo y máximo de la Cadena, verificamos si los personajes en las posiciones de los índices simétricos (derecha e izquierda) son los mismos para cada posición central hasta que lleguemos a nuestro centro máximo de límite superior.

El ciclo externo es O (n) (máx. N-2 iteraciones), y el ciclo interior while es O (n) (máximo alrededor de (n / 2) - 1 iteración)

Aquí está mi implementación de Java usando el ejemplo proporcionado por otros usuarios.

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

El resultado de esto es el siguiente:

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

Answer 11

He escrito el siguiente programa de Java por curiosidad, HTH simple y auto explicativo. Gracias.

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

Answer 12

Hola, aquí está mi código para encontrar el palíndromo más largo de la cadena. Por favor, consulte el siguiente enlace para comprender el algoritmo http://stevekrenzel.com/articles/longest-palnidrome

Los datos de prueba utilizados son 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;     
  }

Answer 13

Me hicieron esta pregunta recientemente. Aquí está la solución con la que finalmente se me ocurrió. Lo hice en JavaScript porque es bastante sencillo en ese idioma.

El concepto básico es que camines la cuerda buscando el palíndromo de múltiples caracteres más pequeño posible (ya sea uno de dos o tres caracteres). Una vez que tenga eso, expanda los bordes en ambos lados hasta que deje de ser un palíndromo. Si esa longitud es más larga que la más larga actual, guárdela y muévase.

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

Esto definitivamente podría limpiarse y optimizarse un poco más, pero debería tener un rendimiento bastante bueno en todos, pero en el peor de los casos (una cadena de la misma letra).

Answer 14

Para la solución lineal, puede usar el algoritmo de Manacher. Hay otro algoritmo llamado Algoritmo de Gusfield, y abajo está el código en 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();  
    }  
}  

Puede encontrar más información sobre otras soluciones, como la mejor solución O (n ^ 2) o el algoritmo de Manacher de mi propio blog .

Answer 15

Pruebe la cadena - "HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE"; Debería funcionar para amigos pares e impares. Muchas gracias a Mohit!

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

Answer 16

Una solución Regexp eficiente que evita la fuerza bruta

Comienza con toda la longitud de la cadena y funciona hacia abajo a 2 caracteres, existe tan pronto como se realiza una coincidencia

Para "abaccddccefe" la "abaccddccefe" prueba 7 coincidencias antes de devolver ccddcc .

(.) (.) (.) (.) (.) (.) (/ 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

función

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

Answer 17

Ver el en.wikipedia.org/wiki/Longest_palindromic_substring sobre este tema. Ejemplo de here implementación de Java here para la solución O (n) lineal del artículo siguiente:

importar java.util.Arrays; clase pública 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;   }     }

Answer 18

con expresiones regulares y rubí puede escanear palíndromos cortos 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

Answer 19

mi solución es:

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

Answer 20

El mejor algoritmo que he encontrado, con complejidad 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;
  }    
}