Keresse meg azokat az alstringeket, amelyek Palindromok a Java-ban

1. Áttekintés

Ebben a gyors bemutatóban különböző megközelítéseket mutatunk be egy adott karaktersorozaton belül minden olyan alstring megtalálása, amely palindróma. Megjegyezzük az egyes megközelítések időbeli összetettségét is.

2. Brute Force megközelítés

Ebben a megközelítésben egyszerűen iteráljuk a bemeneti karakterláncot, hogy megtaláljuk az összes alszöveget. Ugyanakkor ellenőrizni fogjuk, hogy az alszöveg palindrom-e vagy sem:

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)); }}} visszatérő palindromok; }

A fenti példában csak összehasonlítjuk az alszöveget annak fordítottjával, hogy lássuk, palindrom-e:

privát logikai isPalindrome (String input) {StringBuilder sima = new StringBuilder (input); StringBuilder fordított = sima.reverse (); return (reverse.toString ()). egyenlő (input); }

Természetesen könnyen választhatunk számos más megközelítés közül.

E megközelítés időbeli összetettsége O (n ^ 3). Bár ez elfogadható kis bemeneti karakterláncok esetében, hatékonyabb megközelítésre lesz szükségünk, ha nagy mennyiségű szövegben ellenőrizzük a palindrómákat.

3. Centralizációs megközelítés

A központosítási megközelítés ötlete az tekintse az egyes karaktereket forgócsapnak, és táguljon mindkét irányba, hogy palindromokat találjon.

Csak akkor bővítjük, ha a bal és a jobb oldalon lévő karakterek egyeznek, és a karakterláncot palindromnak minősítik. Ellenkező esetben folytatjuk a következő karaktert.

Lássunk egy gyors bemutatót, ahol az egyes karaktereket egy palindrom középpontjának tekintjük:

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)); } visszatérő palindromok; }

A fenti hurkon belül mindkét irányban tágulunk, hogy az összes palindrom halmaza az egyes pozíciókban középre kerüljön. A metódus meghívásával páros és páratlan hosszúságú palindromokat is találunk findPalindromes kétszer a hurokban:

private set findPalindromes (String input, int low, int high) {Set eredmény = új HashSet (); while (alacsony> = 0 && magas <input.length () && input.charAt (alacsony) == input.charAt (magas)) {result.add (input.substring (alacsony, magas + 1)); alacsony--; magas ++; } visszatérési eredmény; }

E megközelítés időbeli összetettsége O (n ^ 2). Ez javulás a nyers erővel kapcsolatos megközelítésünkhöz képest, de ennél is jobban tehetünk, amint azt a következő szakaszban láthatjuk.

4. Manacher algoritmusa

Manacher algoritmusaa lineáris időben megtalálja a leghosszabb palindrom szubsztrátumot. Ezt az algoritmust arra használjuk, hogy megtalálja az összes palindrómás részt.

Mielőtt belevágnánk az algoritmusba, inicializálunk néhány változót.

Először a bemeneti karakterláncot egy kezdő és karakteres karakterrel óvjuk, mielőtt a kapott karakterláncot karaktertömbökké alakítanánk:

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

Ezután kétdimenziós tömböt fogunk használni sugár két sorral - az egyik a páratlan hosszúságú palindromok tárolására szolgál, a másik pedig a páros hosszúságú palindromok tárolására:

int sugár [] [] = új int [2] [input.length () + 1];

Ezután megismételjük a bemeneti tömböt, hogy megtudjuk a palindrom hosszát középre a helyzetben én és ezt a hosszúságot tárolja sugár[][]:

Set palindromes = new HashSet (); int max; for (int j = 0; j <= 1; j ++) {sugár [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 ++; sugár [j] [i] = max; int k = 1; míg (((sugár [j] [i - k]! = max - k) && (k <max)) {sugár [j] [i + k] = Math.min (sugár [j] [i - k], max - k); k ++; } max = Math.max (max - k, 0); i + = k; }}

Végül átmegyünk a tömbön sugár[][] az egyes pozíciók középpontjában levő palindrom részszekvenciák kiszámításához:

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

E megközelítés időbeli összetettsége O (n).

5. Következtetés

Ebben a rövid cikkben a palindrómáknak számító részstruktúrák megkeresésének különböző megközelítései időbeli összetettségét vitattuk meg.

Mint mindig, a példák teljes forráskódja elérhető a GitHubon.


$config[zx-auto] not found$config[zx-overlay] not found