streamalism.org

1. Prehľad

V tomto rýchlom výučbe si ukážeme rôzne prístupy k nájdenie všetkých podreťazcov v danom reťazci, ktoré sú palindrómy. Zaznamenáme tiež časovú zložitosť každého prístupu.

2. Priblíženie hrubou silou

V tomto prístupe jednoducho vykonáme iteráciu nad vstupným reťazcom, aby sme našli všetky podreťazce. Zároveň skontrolujeme, či je podreťazec palindróm alebo nie:

public Set findAllPalindromesUsingBruteForceApproach (reťazcový vstup) {Set palindromes = new HashSet (); pre (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)); }}} vratit palindromy; }

Vo vyššie uvedenom príklade iba porovnáme podreťazec s jeho reverzom, aby sme zistili, či ide o palindróm:

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

Samozrejme si môžeme ľahko zvoliť z niekoľkých ďalších prístupov.

Časová zložitosť tohto prístupu je O (n ^ 3). Aj keď to môže byť prijateľné pre malé vstupné reťazce, pri kontrole palindrómov vo veľkých objemoch textu budeme potrebovať efektívnejší prístup.

3. Centralizačný prístup

Myšlienka centralizovaného prístupu je: zvážte každú postavu ako otočnú čiarku a rozbaľte sa oboma smermi, aby ste našli palindrómy.

Rozbalíme to, iba ak sa znaky na ľavej a pravej strane zhodujú, čím sa reťazec kvalifikuje ako palindróm. Inak pokračujeme k ďalšiemu znaku.

Pozrime sa na krátku ukážku, v ktorej budeme každý znak považovať za stred palindrómu:

public Set findAllPalindromesUsingCenter (reťazcový vstup) {Set palindromes = new HashSet (); pre (int i = 0; i <input.length (); i ++) {palindromes.addAll (findPalindromes (input, i, i + 1)); palindromes.addAll (findPalindromes (vstup, i, i)); } návratové palindrómy; }

V rámci slučky vyššie sa rozširujeme v oboch smeroch, aby sme získali množinu všetkých palindrómov vycentrovaných na každú pozíciu. Palindrómy párnej aj nepárnej dĺžky nájdeme volaním metódy findPalindromes dvakrát v slučke:

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)); nízka--; vysoký ++; } vrátiť výsledok; }

Časová zložitosť tohto prístupu je O (n ^ 2). Toto je zlepšenie oproti nášmu prístupu hrubou silou, ale môžeme to urobiť ešte lepšie, ako uvidíme v nasledujúcej časti.

4. Manacherov algoritmus

Manacherov algoritmusnájde najdlhší palindromický podreťazec v lineárnom čase. Tento algoritmus použijeme na nájdenie všetkých podreťazcov, ktoré sú palindrómmi.

Predtým, ako sa ponoríme do algoritmu, inicializujeme niekoľko premenných.

Najskôr strážime vstupný reťazec hraničným znakom na začiatku a na konci pred konverziou výsledného reťazca na pole znakov:

Reťazec formattedInput = "@" + vstup + "#"; char inputCharArr [] = formattedInput.toCharArray ();

Potom použijeme dvojrozmerné pole polomer s dvoma riadkami - jedným na uloženie dĺžok nepárnych dĺžok palindrómov a druhým na uloženie dĺžok párnych dĺžok palindrómov:

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

Ďalej vykonáme iteráciu nad vstupným poľom, aby sme našli dĺžku palindrómu vycentrovanú na pozíciu i a túto dĺžku uložiť do polomer[][]:

Nastaviť palindromy = nový HashSet (); int max; pre (int j = 0; j <= 1; j ++) {polomer [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 ++; polomer [j] [i] = max; int k = 1; while ((polomer [j] [i - k]! = max - k) && (k <max)) {radius [j] [i + k] = Math.min (polomer [j] [i - k], max - k); k ++; } max = Math.max (max - k, 0); i + = k; }}

Nakoniec prejdeme cez pole polomer[][] na výpočet palindromických podreťazcov so stredom v každej polohe:

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

Časová zložitosť tohto prístupu je O (n).

5. Záver

V tomto rýchlom článku sme diskutovali o časovej zložitosti rôznych prístupov k hľadaniu podreťazcov, ktoré sú palindrómy.

Celý zdrojový kód príkladov je ako vždy k dispozícii na serveri GitHub.