streamalism.org

1. Oversigt

I denne hurtige vejledning gennemgår vi forskellige tilgange til at finde alle understreng i en given streng, der er palindromer. Vi vil også bemærke tidskompleksiteten af ​​hver tilgang.

2. Brute Force-tilgang

I denne tilgang gentager vi simpelthen over inputstrengen for at finde alle understrengene. På samme tid vil vi kontrollere, om understrengen er en palindrom eller ej:

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 omvendte for at se, om det er et palindrom:

privat boolsk isPalindrome (String input) {StringBuilder plain = new StringBuilder (input); StringBuilder reverse = plain.reverse (); return (reverse.toString ()). er lig med (input); }

Selvfølgelig kan vi nemt vælge mellem flere andre tilgange.

Tidskompleksiteten af ​​denne tilgang er O (n ^ 3). Selvom dette kan være acceptabelt for små inputstrenge, har vi brug for en mere effektiv tilgang, hvis vi ser efter palindromer i store mængder tekst.

3. Centraliseringsmetode

Ideen i centraliseringsmetoden er at betragt hvert tegn som omdrejningspunkt og udvid i begge retninger for at finde palindromer.

Vi udvides kun, hvis tegnene i venstre og højre side matcher, hvilket kvalificerer strengen til at være et palindrom. Ellers fortsætter vi til næste tegn.

Lad os se en hurtig demonstration, hvor vi betragter hvert tegn som centrum 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; }

Inden for sløjfen ovenfor udvider vi os i begge retninger for at få sættet af alle palindromer centreret i hver position. Vi finder både lige og ulige længde palindromer ved at kalde metoden findPalindromes to gange i løkken:

private Set findPalindromes (String input, int low, int high) {Set result = new HashSet (); mens (lav> = 0 && høj <input.length () && input.charAt (lav) == input.charAt (høj)) {result.add (input.substring (lav, høj + 1)); lav--; høj ++; } returnere resultat }

Tidskompleksiteten af ​​denne tilgang er O (n ^ 2). Dette er en forbedring i forhold til vores brute-force tilgang, men vi kan gøre det endnu bedre, som vi vil se i det næste afsnit.

4. Manachers algoritme

Manachers algoritmefinder den længste palindromiske understreng i lineær tid. Vi bruger denne algoritme til at finde alle understrenge, der er palindromer.

Før vi dykker ned i algoritmen, initialiserer vi et par variabler.

Først beskytter vi inputstrengen med et grænsetegn i begyndelsen og slutningen, før vi konverterer den resulterende streng til et tegnarray:

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

Derefter bruger vi et todimensionelt array radius med to rækker - en til at gemme længderne af ulige længde palindromer og den anden til at gemme længder af lige længde palindromer:

int-radius [] [] = ny int [2] [input.længde () + 1];

Dernæst gentager vi over inputmatrixen for at finde længden af ​​palindromen centreret i position jeg og opbevar denne længde i radius[][]:

Indstil palindromer = nyt HashSet (); int max; 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], max - k); k ++; } max = Math.max (max - k, 0); i + = k; }}

Endelig krydser vi gennem arrayet radius[][] at beregne de palindromiske substrater centreret i hver 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)); }}}

Tidskompleksiteten af ​​denne tilgang er O (n).

5. Konklusion

I denne hurtige artikel diskuterede vi tidskompleksiteten af ​​forskellige tilgange til at finde understrenge, der er palindromer.

Som altid er den fulde kildekode for eksemplerne tilgængelig på GitHub.