Trouver toutes les sous-chaînes qui sont des palindromes

Cela peut être fait en O(n), à l'aide de Manacher de l'algorithme de.

L'idée principale est une combinaison de la programmation dynamique et (comme d'autres l'ont déjà dit) le calcul de longueur maximum de palindrome avec centre dans une lettre donnée.

---

Ce que nous voulons vraiment pour le calcul est rayon le plus long palindrome, et non pas la longueur.
Le rayon est tout simplement length/2 ou (length - 1)/2 (de longueur impaire palindromes).

Après le calcul de palindrome rayon pr à une position donnée i nous utilisons déjà calculés rayons de trouver des palindromes dans la gamme [i - pr ; i]. Cela vous permet de nous (parce que les palindromes sont, ainsi, les palindromes) ignorer les autres le calcul de radiuses de gamme [i ; i + pr].

Alors que l'on recherche dans la gamme [i - pr ; i], il existe quatre cas pour chaque position i - k (où k est dans 1,2,... pr):

• pas de palindrome (radius = 0) à i - k
  
  (cela signifie radius = 0 à i + k, trop)
• intérieure palindrome, ce qui signifie qu'il s'inscrit dans la gamme
  
  (cela signifie radius à i + k est la même qu'au i - k)
• extérieur palindrome, ce qui signifie qu'il ne rentre pas dans la gamme
  
  (cela signifie radius à i + k est couper pour s'adapter à portée, j'.e parce que i + k + radius > i + pr nous réduire radius à pr - k)
• collant palindrome, ce qui signifie i + k + radius = i + pr
  
  (dans ce cas, nous avons besoin de la recherche pour potentiellement plus grand rayon de i + k)

Complet, détaillé, l'explication serait plutôt le long. Les exemples de code? 🙂

J'ai trouvé C++ mise en œuvre de cet algorithme par un professeur de polonais, mgr Jerzy Wałaszek.

J'ai traduit les commentaires de l'anglais, ajouté quelques autres commentaires et simplifié un peu d'être plus faciles à attraper la pièce principale.

Jetez un oeil ici.

---

Remarque: en cas de difficultés à comprendre pourquoi c'est O(n), essayez de regarder de cette façon:

après avoir trouvé rayon (appelons r), à une position, nous avons besoin d'itérer sur r éléments de retour, mais comme un résultat, nous pouvons ignorer le calcul pour les r éléments de l'avant. Par conséquent, le nombre total de itéré éléments reste le même.

Donc, chaque lettre est déjà un palindrome si vous avez déjà N + 1 palindromes, où N est le nombre de lettres distinctes (plus une chaîne vide). Vous pouvez le faire que dans un seul d'exécution O(N).

Maintenant, pour les non-trivial palindromes, vous pouvez tester chaque point de la chaîne pour être un centre de potentiel palindrome - se développer dans deux directions - quelque chose qui Valentin Ruano suggéré.

Cette solution permettra de prendre en O(N^2) étant donné que chaque test est O(N) et le nombre de "centres" est également en O(N) - le center est une lettre ou un espace entre deux lettres, là encore, comme dans Valentin solution.

Note, il est également en O(N), solution à votre problème, basée sur Manacher de l' algorithme (article décrit "le plus long palindrome", mais l'algorithme peut être utilisé pour compter tous d'entre eux)

Je suggère la construction d'une base de cas et l'expansion jusqu'à ce que vous avez tous les palindomes.

Il existe deux types de palindromes: paires et impaires. Je n'ai pas compris comment gérer à la fois de la même manière donc je vais le briser.

1) Ajouter toutes les lettres

2) Avec cette liste, vous avez tous les points de départ pour votre palindromes. Exécuter chaque fois pour chaque index dans la chaîne (ou 1 -> longueur-1, parce que vous avez besoin d'au moins 2 longueur):

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

Je ne sais pas si cela aide le Big-O pour votre runtime, mais il devrait être beaucoup plus efficace que de tenter de chaque sous-chaîne. Pire des cas serait une chaîne de toutes la même lettre, ce qui peut être pire que le "trouver tous les sous-chaîne" plan, mais avec la plupart des intrants, il coupera la plupart des sous-chaînes parce que vous pouvez arrêter de regarder une fois que vous réalisez ce n'est pas le centre d'un palindrome.

J'ai essayé le code suivant et sa fonctionne bien pour le cas
Aussi, il gère les différents caractères trop

Peu de cas qui est passé:

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]

Code

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

Espoir, ses beaux -

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

Essayer ce. Sa ma propre solution.