streamalism.org

1. Oversikt

I denne raske opplæringen vil vi gå gjennom forskjellige tilnærminger til finne alle understreng i en gitt streng som er palindromer. Vi vil også merke seg tidskompleksiteten til hver tilnærming.

2. Brute Force-tilnærming

I denne tilnærmingen vil vi ganske enkelt gjenta over inngangsstrengen for å finne alle understrengene. Samtidig vil vi sjekke om undergrunnen er en palindrom eller ikke:

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

I eksemplet ovenfor sammenligner vi bare substringen med dens revers for å se om det er en palindrom:

private boolean isPalindrome (String input) {StringBuilder plain = new StringBuilder (input); StringBuilder revers = vanlig.omvendt (); return (revers.toString ()). er lik (input); }

Selvfølgelig kan vi enkelt velge mellom flere andre tilnærminger.

Tidskompleksiteten til denne tilnærmingen er O (n ^ 3). Selv om dette kan være akseptabelt for små inngangsstrenger, trenger vi en mer effektiv tilnærming hvis vi ser etter palindromer i store mengder tekst.

3. Sentraliseringstilnærming

Ideen i sentraliseringstilnærmingen er å betrakt hvert tegn som dreiepunkt og utvid i begge retninger for å finne palindromer.

Vi utvider bare hvis tegnene på venstre og høyre side samsvarer, og kvalifiserer strengen til å være et palindrom. Ellers fortsetter vi til neste karakter.

La oss se en rask demonstrasjon der vi vil betrakte hvert tegn som sentrum for et palindrom:

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

Innenfor løkken over utvider vi oss i begge retninger for å få settet med alle palindromer sentrert i hver posisjon. Vi finner både jevne og merkelige palindromer ved å kalle metoden finnPalindromes to ganger i løkken:

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)); lav--; høy ++; } returnere resultat; }

Tidskompleksiteten til denne tilnærmingen er O (n ^ 2). Dette er en forbedring i forhold til vår brute-force-tilnærming, men vi kan gjøre det enda bedre, som vi vil se i neste avsnitt.

4. Manachers algoritme

Manachers algoritmefinner det lengste palindromiske substratet på lineær tid. Vi bruker denne algoritmen til å finne alle understreng som er palindromer.

Før vi dykker inn i algoritmen, initialiserer vi noen få variabler.

Først vil vi beskytte inngangsstrengen med et grensetegn i begynnelsen og slutten før vi konverterer den resulterende strengen til et tegnmatrise:

Streng formattedInput = "@" + inngang + "#"; char inputCharArr [] = formattedInput.toCharArray ();

Deretter bruker vi en todimensjonal matrise radius med to rader - en for å lagre lengdene på oddelengde palindromer, og den andre for å lagre lengder av jevnlengde palindromer:

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

Deretter vil vi iterere over inngangsmatrisen for å finne lengden på palindromen sentrert i posisjon Jeg og lagre denne lengden i radius[][]:

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

Til slutt vil vi krysse gjennom matrisen radius[][] for å beregne de palindromiske understrengene sentrert i hver posisjon:

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

Tidskompleksiteten til denne tilnærmingen er O (n).

5. Konklusjon

I denne raske artikkelen diskuterte vi tidskompleksiteten til forskjellige tilnærminger for å finne underlag som er palindromer.

Som alltid er hele kildekoden til eksemplene tilgjengelig på GitHub.