streamalism.org

1. Overzicht

In deze korte handleiding bespreken we verschillende benaderingen van het vinden van alle subtekenreeksen binnen een gegeven string die palindromen zijn. We zullen ook de tijdcomplexiteit van elke benadering noteren.

2. Brute Force-aanpak

In deze benadering herhalen we eenvoudig de invoertekenreeks om alle subtekenreeksen te vinden. Tegelijkertijd zullen we controleren of de deelstring een palindroom is of niet:

public Set findAllPalindromesUsingBruteForceApproach (String-invoer) {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)); }}} terugkeer palindromen; }

In het bovenstaande voorbeeld vergelijken we de deelstring met zijn omgekeerde om te zien of het een palindroom is:

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

Natuurlijk kunnen we gemakkelijk kiezen uit verschillende andere benaderingen.

De tijdcomplexiteit van deze benadering is O (n ^ 3). Hoewel dit acceptabel kan zijn voor kleine invoertekenreeksen, hebben we een efficiëntere aanpak nodig als we zoeken naar palindromen in grote tekstvolumes.

3. Centralisatiebenadering

Het idee in de centralisatiebenadering is om beschouw elk personage als de spil en breid in beide richtingen uit om palindromen te vinden.

We breiden alleen uit als de tekens aan de linker- en rechterkant overeenkomen, waardoor de tekenreeks wordt gekwalificeerd als een palindroom. Anders gaan we verder naar het volgende personage.

Laten we een korte demonstratie bekijken waarin we elk personage beschouwen als het centrum van een palindroom:

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

Binnen de bovenstaande lus breiden we uit in beide richtingen om de verzameling van alle palindromen gecentreerd op elke positie te krijgen. We zullen palindromen met zowel even als oneven lengte vinden door de methode aan te roepen vind palindromen twee keer in de lus:

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

De tijdcomplexiteit van deze benadering is O (n ^ 2). Dit is een verbetering ten opzichte van onze brute-force-aanpak, maar we kunnen het nog beter doen, zoals we in de volgende sectie zullen zien.

4. Manacher's algoritme

Het algoritme van Manachervindt de langste palindrome deelstring in lineaire tijd. We gebruiken dit algoritme om alle subtekenreeksen te vinden die palindromen zijn.

Voordat we in het algoritme duiken, initialiseren we een paar variabelen.

Eerst bewaken we de invoertekenreeks met een begrenzingsteken aan het begin en einde voordat we de resulterende tekenreeks naar een tekenreeks converteren:

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

Vervolgens gebruiken we een tweedimensionale array straal met twee rijen - één om de lengtes van palindromen van oneven lengte op te slaan en de andere om lengtes van palindromen van even lengte op te slaan:

int straal [] [] = nieuwe int [2] [input.length () + 1];

Vervolgens herhalen we de invoerarray om de lengte van het palindroom gecentreerd op positie te vinden ik en sla deze lengte op in straal[][]:

Set palindromes = new HashSet (); int max; voor (int j = 0; j <= 1; j ++) {straal [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 ++; straal [j] [i] = max; int k = 1; while ((straal [j] [i - k]! = max - k) && (k <max)) {straal [j] [i + k] = Math.min (straal [j] [i - k], max - k); k ++; } max = Math.max (max - k, 0); ik + = k; }}

Ten slotte zullen we door de array bladeren straal[][] om de palindrome substrings gecentreerd op elke positie te berekenen:

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

De tijdcomplexiteit van deze benadering is O (n).

5. Conclusie

In dit korte artikel bespraken we de tijdcomplexiteit van verschillende benaderingen om substrings te vinden die palindromen zijn.

Zoals altijd is de volledige broncode van de voorbeelden beschikbaar op GitHub.