java - saber - Encuentra todas las subcadenas que son palíndromos.

programa de palindromo en netbeans

Question

Si la entrada es ''abba'', los posibles palíndromos son a, b, b, a, bb, abba.
Entiendo que determinar si la cadena es palíndromo es fácil. Sería como:

public static boolean isPalindrome(String str) {
 int len = str.length();
 for(int i=0; i<len/2; i++) {
     if(str.charAt(i)!=str.charAt(len-i-1) {
         return false;
     }
 return true;  
}

Pero, ¿cuál es la forma eficiente de encontrar subcadenas de palíndromo?

Answer 1

Esto se puede hacer en O(n) , usando el algoritmo de Manacher .

La idea principal es una combinación de programación dinámica y (como otros ya han dicho) calcular la longitud máxima del palíndromo con el centro en una letra determinada.

Lo que realmente queremos calcular es el radio del palíndromo más largo, no la longitud. El radio es simplemente length/2 o (length - 1)/2 (para palíndromos de longitud impar).

Después de calcular la radio pr palíndromo en la posición i , usamos radios ya calculados para encontrar palíndromos en el rango [ i - pr ; i i - pr ; i ] . Esto nos permite (porque los palíndromos son, bueno, palíndromos) omitir más cálculos de radiuses para rango [ i ; i + pr i ; i + pr ] .

Mientras buscamos en rango [ i - pr ; i i - pr ; i ] , hay cuatro casos básicos para cada posición i - k (donde k está en 1,2,... pr ):

• sin palíndromo ( radius = 0 ) en i - k
  (esto significa radius = 0 en i + k , también)
• palíndromo interno , lo que significa que encaja dentro del rango
  (esto significa que el radius en i + k es el mismo que en i - k )
• palíndromo exterior , lo que significa que no encaja dentro del rango
  (Esto significa que el radius en i + k se reduce para ajustarse al rango, es decir, porque i + k + radius > i + pr reducimos el radius a pr - k )
• palíndromo pegajoso , que significa i + k + radius = i + pr
  (en ese caso debemos buscar un radio potencialmente mayor en i + k )

La explicación completa y detallada sería bastante larga. ¿Qué pasa con algunos ejemplos de código? :)

He encontrado la implementación en C ++ de este algoritmo por parte del profesor polaco, el Sr. Jerzy Wałaszek.
He traducido comentarios al inglés, he agregado algunos otros comentarios y lo he simplificado un poco para que sea más fácil captar la parte principal.
Echa un vistazo aquí .

Nota: en caso de problemas para entender por qué esto es O(n) , intente mirar de esta manera:
después de encontrar el radio (llamémoslo r ) en alguna posición, necesitamos iterar sobre r elementos hacia atrás, pero como resultado podemos omitir el cálculo para r elementos hacia adelante. Por lo tanto, el número total de elementos iterados permanece igual.

Answer 2

Acabo de idear mi propia lógica que ayuda a resolver este problema. Feliz codificación .. :-)

System.out.println("Finding all palindromes in a given string : ");
        subPal("abcacbbbca");

private static void subPal(String str) {
        String s1 = "";
        int N = str.length(), count = 0;
        Set<String> palindromeArray = new HashSet<String>();
        System.out.println("Given string : " + str);
        System.out.println("******** Ignoring single character as substring palindrome");
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                int k = i + j - 1;
                if (k >= N)
                    continue;
                s1 = str.substring(j, i + j);
                if (s1.equals(new StringBuilder(s1).reverse().toString())) {
                    palindromeArray.add(s1);
                }
            }

        }
        System.out.println(palindromeArray);
        for (String s : palindromeArray)
            System.out.println(s + " - is a palindrome string.");
        System.out.println("The no.of substring that are palindrome : "
                + palindromeArray.size());
    }

Output:-
Finding all palindromes in a given string : 
Given string : abcacbbbca
******** Ignoring single character as substring palindrome ********
[cac, acbbbca, cbbbc, bb, bcacb, bbb]
cac - is a palindrome string.
acbbbca - is a palindrome string.
cbbbc - is a palindrome string.
bb - is a palindrome string.
bcacb - is a palindrome string.
bbb - is a palindrome string.
The no.of substring that are palindrome : 6

Answer 3

El código es encontrar todas las subcadenas distintas que son palíndromo. Aquí está el código que probé. Está funcionando bien.

import java.util.HashSet;
import java.util.Set;

public class SubstringPalindrome {

    public static void main(String[] args) {
        String s = "abba";
        checkPalindrome(s);
}

public static int checkPalindrome(String s) {
    int L = s.length();
    int counter =0;
    long startTime = System.currentTimeMillis();
    Set<String> hs = new HashSet<String>();
    // add elements to the hash set
    System.out.println("Possible substrings: ");
    for (int i = 0; i < L; ++i) {
      for (int j = 0; j < (L - i); ++j) {
          String subs = s.substring(j, i + j + 1);
            counter++;
            System.out.println(subs);
            if(isPalindrome(subs))
                hs.add(subs);
      }
    }
    System.out.println("Total possible substrings are "+counter);
    System.out.println("Total palindromic substrings are "+hs.size());
    System.out.println("Possible palindromic substrings: "+hs.toString());
    long endTime = System.currentTimeMillis();
    System.out.println("It took " + (endTime - startTime) + " milliseconds");
    return hs.size();
}
public static boolean isPalindrome(String s) {
    if(s.length() == 0 || s.length() ==1)
        return true;
    if(s.charAt(0) ==  s.charAt(s.length()-1))
        return isPalindrome(s.substring(1, s.length()-1));
    return false;
}

}

SALIDA:

Posibles subcadenas: a b b a ab bb ba abb bba abba

Total de subcadenas posibles son 10

Las subcadenas palindrómicas totales son 4.

Posibles subcadenas palindrómicas: [bb, a, b, abba]

Le tomó 1 milisegundos

Answer 4

Por lo tanto, cada letra distinta ya es un palíndromo, por lo que ya tiene N + 1 palíndromos, donde N es el número de letras distintas (más una cadena vacía). Usted puede hacer eso en una sola carrera - O (N).

Ahora, para palíndromos no triviales, puedes probar cada punto de tu cuerda para que sea un centro de palíndromos potenciales, crecer en ambas direcciones, algo que sugirió Valentin Ruano .
Esta solución tomará O (N ^ 2) ya que cada prueba es O (N) y el número de posibles "centros" también es O (N): el center es una letra o un espacio entre dos letras, nuevamente como en la solución de Valentin.

Tenga en cuenta que también hay una solución O (N) para su problema, basada en el Manacher''s Manacher (el artículo describe "palíndromo más largo", pero el algoritmo se podría usar para contarlos todos)

Answer 5

Probé el siguiente código y está funcionando bien para los casos. También maneja caracteres individuales también.

Pocos de los casos que pasaron:

abaaa --> [aba, aaa, b, a, aa] 
geek  --> [g, e, ee, k] 
abbaca --> [b, c, a, abba, bb, aca] 
abaaba -->[aba, b, abaaba, a, baab, aa] 
abababa -->[aba, babab, b, a, ababa, abababa, bab] 
forgeeksskeegfor --> [f, g, e, ee, s, r, eksske, geeksskeeg, 
                      o, eeksskee, ss, k, kssk]

Código

static Set<String> set = new HashSet<String>(); 
static String DIV = "|";

public static void main(String[] args) {
    String str = "abababa";
    String ext = getExtendedString(str);

    // will check for even length palindromes
    for(int i=2; i<ext.length()-1; i+=2) {
        addPalindromes(i, 1, ext);
    }
    // will check for odd length palindromes including individual characters
    for(int i=1; i<=ext.length()-2; i+=2) {
        addPalindromes(i, 0, ext);
    }
    System.out.println(set);
}

/*
 * Generates extended string, with dividors applied
 * eg: input = abca
 * output = |a|b|c|a|
 */
static String getExtendedString(String str) {
    StringBuilder builder = new StringBuilder();
    builder.append(DIV);
    for(int i=0; i< str.length(); i++) {
        builder.append(str.charAt(i));
        builder.append(DIV);

    }
    String ext = builder.toString();
    return ext;
}

/*
 * Recursive matcher
 * If match is found for palindrome ie char[mid-offset] = char[mid+ offset]
 * Calculate further with offset+=2
 * 
 * 
 */
static void addPalindromes(int mid, int offset, String ext) {
    // boundary checks
    if(mid - offset <0 || mid + offset > ext.length()-1) {
        return;
    }
    if (ext.charAt(mid-offset) == ext.charAt(mid+offset)) {
        set.add(ext.substring(mid-offset, mid+offset+1).replace(DIV, ""));
        addPalindromes(mid, offset+2, ext);
    }
}

Espero que esta bien

Answer 6

Sugiero construir desde un caso base y expandir hasta que tenga todos los palindomes.

Hay dos tipos de palíndromos: pares e impares. No he descubierto cómo manejar ambos de la misma manera, así que lo separaré.

1) Añadir todas las letras individuales

2) Con esta lista tienes todos los puntos de partida para tus palíndromos. Ejecute cada uno de estos dos para cada índice en la cadena (o 1 -> longitud-1 porque necesita al menos 2 longitud):

findAllEvenFrom(int index){
  int i=0;
  while(true) {
    //check if index-i and index+i+1 is within string bounds

    if(str.charAt(index-i) != str.charAt(index+i+1)) 
      return; // Here we found out that this index isn''t a center for palindromes of >=i size, so we can give up

    outputList.add(str.substring(index-i, index+i+1));
    i++;
  }
}
//Odd looks about the same, but with a change in the bounds.
findAllOddFrom(int index){
  int i=0;
  while(true) {
    //check if index-i and index+i+1 is within string bounds

    if(str.charAt(index-i-1) != str.charAt(index+i+1)) 
      return;

    outputList.add(str.substring(index-i-1, index+i+1));
    i++;
  }
}

No estoy seguro de si esto ayuda al Big-O en su tiempo de ejecución, pero debería ser mucho más eficiente que probar cada subcadena. El peor de los casos sería una cadena de la misma letra que podría ser peor que el plan de "encontrar cada subcadena", pero con la mayoría de las entradas, eliminará la mayoría de las subcadenas porque puede dejar de mirar una una vez que se dé cuenta de que no es el centro de una palíndromo.

Answer 7

Tal vez podría recorrer los caracteres intermedios potenciales (palíndromos de longitud impar) y los puntos intermedios entre los caracteres (palíndromos de longitud par) y extender cada uno hasta que no pueda continuar (los siguientes caracteres de la izquierda y la derecha no coinciden).

Eso ahorraría muchos cálculos cuando no hay muchos palidromes en la cadena. En tal caso, el costo sería O (n) para cadenas de palidrome dispersas.

Para las entradas densas de palíndromos, sería O (n ^ 2) ya que cada posición no puede extenderse más que la longitud de la matriz / 2. Obviamente, esto es aún menos hacia los extremos de la matriz.

  public Set<String> palindromes(final String input) {

     final Set<String> result = new HashSet<>();

     for (int i = 0; i < input.length(); i++) {
         // expanding even length palindromes:
         expandPalindromes(result,input,i,i+1);
         // expanding odd length palindromes:
         expandPalindromes(result,input,i,i);
     } 
     return result;
  }

  public void expandPalindromes(final Set<String> result, final String s, int i, int j) {
      while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            result.add(s.substring(i,j+1));
            i--; j++;
      }
  }

Answer 8

public class PolindromeMyLogic {

static int polindromeCount = 0;

private static HashMap<Character, List<Integer>> findCharAndOccurance(
        char[] charArray) {
    HashMap<Character, List<Integer>> map = new HashMap<Character, List<Integer>>();
    for (int i = 0; i < charArray.length; i++) {
        char c = charArray[i];
        if (map.containsKey(c)) {
            List list = map.get(c);
            list.add(i);
        } else {
            List list = new ArrayList<Integer>();
            list.add(i);
            map.put(c, list);
        }
    }
    return map;
}

private static void countPolindromeByPositions(char[] charArray,
        HashMap<Character, List<Integer>> map) {
    map.forEach((character, list) -> {
        int n = list.size();
        if (n > 1) {
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (list.get(i) + 1 == list.get(j)
                            || list.get(i) + 2 == list.get(j)) {
                        polindromeCount++;
                    } else {
                        char[] temp = new char[(list.get(j) - list.get(i))
                                + 1];
                        int jj = 0;
                        for (int ii = list.get(i); ii <= list
                                .get(j); ii++) {
                            temp[jj] = charArray[ii];
                            jj++;
                        }
                        if (isPolindrome(temp))
                            polindromeCount++;
                    }

                }
            }
        }
    });
}

private static boolean isPolindrome(char[] charArray) {
    int n = charArray.length;
    char[] temp = new char[n];
    int j = 0;
    for (int i = (n - 1); i >= 0; i--) {
        temp[j] = charArray[i];
        j++;
    }
    if (Arrays.equals(charArray, temp))
        return true;
    else
        return false;
}

public static void main(String[] args) {
    String str = "MADAM";
    char[] charArray = str.toCharArray();
    countPolindromeByPositions(charArray, findCharAndOccurance(charArray));
    System.out.println(polindromeCount);
}
}

Prueba esto. Es mi propia solución.

Answer 9

    // Maintain an Set of palindromes so that we get distinct elements at the end
    // Add each char to set. Also treat that char as middle point and traverse through string to check equality of left and right char


static int palindrome(String str) {

    Set<String> distinctPln = new HashSet<String>();
    for (int i=0; i<str.length();i++) {
        distinctPln.add(String.valueOf(str.charAt(i)));
        for (int j=i-1, k=i+1; j>=0 && k<str.length(); j--, k++) {
            // String of lenght 2 as palindrome
            if ( (new Character(str.charAt(i))).equals(new Character(str.charAt(j)))) { 
                distinctPln.add(str.substring(j,i+1));
            }
            // String of lenght 2 as palindrome
            if ( (new Character(str.charAt(i))).equals(new Character(str.charAt(k)))) { 
                distinctPln.add(str.substring(i,k+1));
            }
            if ( (new Character(str.charAt(j))).equals(new Character(str.charAt(k)))) { 
                distinctPln.add(str.substring(j,k+1));
            } else {
                continue;
            }
        }
    }

    Iterator<String> distinctPlnItr = distinctPln.iterator();
    while ( distinctPlnItr.hasNext()) {
        System.out.print(distinctPlnItr.next()+ ",");
    }
    return distinctPln.size();

}