Manacher Algoritması

Dizeler O(n) O(n)

Merkezler etrafında genişleyip yarıçapları mevcut palindrom boyunca yansıtarak en uzun palindrom alt dizeyi doğrusal zamanda bulur.

transform

^·0

#·1

A·2

#·3

B·4

#·5

A·6

#·7

B·8

#·9

A·10

#·11

B·12

#·13

A·14

#·15

$·16

Metin

i=0c=0r=0

1/39

Merkez c ve sağ kenar r 0'dan başlıyor.

Değişmezp[i], i merkezli palindromun yarıçapıdır. Bilinen pencere içinde bu yarıçap aynalanır, böylece hiçbir karakter iki kez karşılaştırılmaz.

işaretçieşleşmeuyumsuzpencere

manacher.c

/* transform: "aba" -> "^#a#b#a#$" */
int manacher(const char *t, int n, int p[]) {
    int c = 0, r = 0, best = 0;
    for (int i = 1; i < n - 1; i++) {
        if (i < r)
            p[i] = min(r - i, p[2 * c - i]);
        while (t[i + p[i] + 1] == t[i - p[i] - 1])
            p[i]++;
        if (i + p[i] > r) {
            c = i;
            r = i + p[i];
        }
        if (p[i] > best) best = p[i];
    }
    return best;
}

Manacher Algoritması nasıl çalışır?

Her palindromu tek uzunluklu yapmak için ayraçlar ekle, sonra her merkezden genişle — ama önce her yarıçapı, mevcut en sağ palindromun içindeki aynasından tohumla. Her karakter en fazla bir kez genişletilir.

Ne zaman kullanılır?

O(n)'de en uzun palindrom alt dize; palindrom sayma ve çarpanlama.