Rechercher des sous-chaînes qui sont des palindromes en Java

1. Vue d'ensemble

Dans ce rapide didacticiel, nous allons passer par différentes approches pour trouver toutes les sous-chaînes d'une chaîne donnée qui sont des palindromes . Nous noterons également la complexité temporelle de chaque approche.

2. Approche par force brute

Dans cette approche, nous allons simplement parcourir la chaîne d'entrée pour trouver toutes les sous-chaînes. En même temps, nous vérifierons si la sous-chaîne est un palindrome ou non:

public Set findAllPalindromesUsingBruteForceApproach(String input) { Set palindromes = new HashSet(); for (int i = 0; i < input.length(); i++) { for (int j = i + 1; j <= input.length(); j++) { if (isPalindrome(input.substring(i, j))) { palindromes.add(input.substring(i, j)); } } } return palindromes; }

Dans l'exemple ci-dessus, nous comparons simplement la sous-chaîne à son inverse pour voir s'il s'agit d'un palindrome:

private boolean isPalindrome(String input) { StringBuilder plain = new StringBuilder(input); StringBuilder reverse = plain.reverse(); return (reverse.toString()).equals(input); }

Bien entendu, nous pouvons facilement choisir parmi plusieurs autres approches.

La complexité temporelle de cette approche est O (n ^ 3). Bien que cela puisse être acceptable pour les petites chaînes d'entrée, nous aurons besoin d'une approche plus efficace si nous vérifions les palindromes dans de grands volumes de texte.

3. Approche de centralisation

L'idée dans l'approche de centralisation est de considérer chaque personnage comme le pivot et de s'étendre dans les deux sens pour trouver des palindromes .

Nous ne développerons que si les caractères à gauche et à droite correspondent, qualifiant la chaîne de palindrome. Sinon, nous passons au personnage suivant.

Voyons une démonstration rapide dans laquelle nous considérerons chaque personnage comme le centre d'un palindrome:

public Set findAllPalindromesUsingCenter(String input) { Set palindromes = new HashSet(); for (int i = 0; i < input.length(); i++) { palindromes.addAll(findPalindromes(input, i, i + 1)); palindromes.addAll(findPalindromes(input, i, i)); } return palindromes; }

Dans la boucle ci-dessus, nous développons dans les deux directions pour obtenir l'ensemble de tous les palindromes centrés à chaque position. Nous trouverons des palindromes de longueur paire et impaire en appelant la méthode findPalindromes deux fois dans la boucle :

private Set findPalindromes(String input, int low, int high) { Set result = new HashSet(); while (low >= 0 && high < input.length() && input.charAt(low) == input.charAt(high)) { result.add(input.substring(low, high + 1)); low--; high++; } return result; }

La complexité temporelle de cette approche est O (n ^ 2). C'est une amélioration par rapport à notre approche de la force brute, mais nous pouvons faire encore mieux, comme nous le verrons dans la section suivante.

4. Algorithme de Manacher

L'algorithme de Manacher trouve la plus longue sous-chaîne palindromique en temps linéaire . Nous utiliserons cet algorithme pour trouver toutes les sous-chaînes qui sont des palindromes.

Avant de plonger dans l'algorithme, nous initialiserons quelques variables.

Tout d'abord, nous allons garder la chaîne d'entrée avec un caractère de limite au début et à la fin avant de convertir la chaîne résultante en un tableau de caractères:

String formattedInput = "@" + input + "#"; char inputCharArr[] = formattedInput.toCharArray();

Ensuite, nous utiliserons un rayon de tableau à deux dimensions avec deux lignes - une pour stocker les longueurs des palindromes de longueur impaire, et l'autre pour stocker les longueurs de palindromes de longueur paire:

int radius[][] = new int[2][input.length() + 1];

Ensuite, nous allons parcourir le tableau d'entrée pour trouver la longueur du palindrome centré à la position i et stocker cette longueur dans le rayon [] [] :

Set palindromes = new HashSet(); int max; for (int j = 0; j <= 1; j++) { radius[j][0] = max = 0; int i = 1; while (i <= input.length()) { palindromes.add(Character.toString(inputCharArr[i])); while (inputCharArr[i - max - 1] == inputCharArr[i + j + max]) max++; radius[j][i] = max; int k = 1; while ((radius[j][i - k] != max - k) && (k < max)) { radius[j][i + k] = Math.min(radius[j][i - k], max - k); k++; } max = Math.max(max - k, 0); i += k; } }

Enfin, nous traverserons le rayon du tableau [] [] pour calculer les sous-chaînes palindromiques centrées à chaque position:

for (int i = 1; i <= input.length(); i++) { for (int j = 0; j  0; max--) { palindromes.add(input.substring(i - max - 1, max + j + i - 1)); } } }

La complexité temporelle de cette approche est O (n).

5. Conclusion

Dans cet article rapide, nous avons discuté de la complexité temporelle des différentes approches pour trouver des sous-chaînes qui sont des palindromes.

Comme toujours, le code source complet des exemples est disponible à l'adresse over sur GitHub.