Алгоритми Манакер

Алгоритми Манакер - Course 5

t

=

t_{r e v}

t = t_{rev}

Агар $i$ берун аз зерпалиндроми ҷорӣ бошад, яъне $i \geq r$ , мо метавонем равиши соддаи дар боло тавсифшударо истифода барем.
Агар $i \le r$ , биёед мавқеи "оина"-и $i$ -ро дар зерпалиндроми $(l, r)$ ёбем, яъне мавқеи $j = l + (r - i)$ -ро мегирем, ва қимати $d_{odd}[j]$ -ро месанҷем. Азбаски $j$ мавқеи симметрии $i$ нисбат ба $(l+r)/2$ аст, мо қариб ҳамеша метавонем $d_{odd}[i] = d_{odd}[j]$ таъин кунем. Тасвири ин (палиндроми атрофи $j$ воқеан ба палиндроми атрофи $i$ "нусха" мешавад): $\ldots\ \overbrace{ s_{l+1}\ \ldots\ \underbrace{ s_{j-d_{odd}[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_{odd}[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ s_{r-1}\ }^\text{palindrome}\ \ldots$ Ҳолати ҳиллагарона метавонад он бошад, ки палиндроми "дарунӣ" ба сарҳадҳои "берунӣ" мерасад, яъне $j - d_{odd}[j] \le l$ (ё, ки ҳамон аст, $i + d_{odd}[j] \ge r$ ). Азбаски симметрия берун аз палиндроми "берунӣ" кафолат дода намешавад, танҳо таъин кардани $d_{odd}[i] = d_{odd}[j]$ нодуруст хоҳад буд: мо маълумоти кофӣ надорем, то бигӯем, ки палиндром дар мавқеи $i$ ҳамон дарозиро дорад.

vector<int> adjustedManacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = oddLengthManacher(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}

Алгоритми Манакер

Муқаддима

Алгоритм

Равиши содда

Алгоритми Манакер барои сатри дарозии тоқ

Алгоритми Манакер барои ҳолати умумӣ