Агуулгыг алгасах

Давталт олох

$n$ урттай $s$ тэмдэгт мөр өгөгдсөн.

Давталт гэдэг нь тэмдэгт мөрийн дараалсан хоёр орц юм. Өөрөөр хэлбэл давталтыг $s[i \dots j]$ дэд мөр нь дараалан бичигдсэн хоёр ижил тэмдэгт мөрөөс бүрдэх байх $i < j$ индексийн хосоор тодорхойлж болно.

Даалгавар нь өгөгдсөн $s$ тэмдэгт мөр дэх бүх давталтыг олох явдал юм. Эсвэл хялбарчилсан бодлого: дурын давталтыг ол эсвэл хамгийн урт давталтыг ол.

Энд тайлбарласан алгоритмыг Main, Lorentz нар 1982 онд нийтэлсэн.

Жишээ

Дараах жишээ тэмдэгт мөр дэх давталтуудыг авч үзье:

$$acababaee$$

Тэмдэгт мөр дараах гурван давталтыг агуулна:

  • $s[2 \dots 5] = abab$
  • $s[3 \dots 6] = baba$
  • $s[7 \dots 8] = ee$

Өөр нэг жишээ:

$$abaaba$$

Энд ердөө хоёр давталт байна

  • $s[0 \dots 5] = abaaba$
  • $s[2 \dots 3] = aa$

Давталтын тоо

Ерөнхийдөө $n$ урттай тэмдэгт мөрд $O(n^2)$ хүртэл давталт байж болно. Илэрхий жишээ бол ижил үсгийг $n$ удаа давтсанаас бүрдэх тэмдэгт мөр бөгөөд энэ тохиолдолд тэгш урттай дурын дэд мөр нь давталт болно. Ерөнхийдөө богино үетэй дурын үечилсэн тэмдэгт мөр олон давталт агуулна.

Нөгөө талаас энэ баримт нь давталтын тоог $O(n \log n)$ хугацаанд тооцоолоход саад болохгүй, учир нь алгоритм давталтуудыг шахсан хэлбэрээр, хэд хэдэн хэсгийн бүлгээр нэг дор өгч чадна.

Үечилсэн дэд мөрүүдийн бүлгийг дөрвөн хэмжээст кортежаар тодорхойлдог ойлголт хүртэл бий. Ийм бүлгийн тоо тэмдэгт мөрийн уртын хувьд хамгийн ихдээ шугаман байдаг нь батлагдсан.

Мөн давталтын тоотой холбоотой бусад сонирхолтой үр дүнгүүд энд байна:

  • Анхдагч давталтын (хагасууд нь давталт биш байх давталтууд) тоо хамгийн ихдээ $O(n \log n)$ байна.
  • Хэрэв бид давталтуудыг тоонуудын кортежаар (Crochemore-ийн гурвал гэж нэрлэдэг) $(i,~ p,~ r)$ кодчилвол (энд $i$ нь эхлэлийн байрлал, $p$ нь давтагдаж буй дэд мөрийн урт, $r$ нь давталтын тоо) бүх давталтыг $O(n \log n)$ ийм гурвалаар тодорхойлж болно.

  • Дараах байдлаар тодорхойлогдох Фибоначчийн тэмдэгт мөрүүд

    $$\begin{align} t_0 &= a, \\\\ t_1 &= b, \\\\ t_i &= t_{i-1} + t_{i-2}, \end{align}$$

    нь "хүчтэй" үечилсэн байна. Фибоначчийн тэмдэгт мөр $f_i$ дэх давталтын тоо, бүр Crochemore-ийн гурвалаар шахсан ч $O(f_n \log f_n)$ байна. Анхдагч давталтын тоо мөн $O(f_n \log f_n)$ юм.

Main-Lorentz-ийн алгоритм

Main-Lorentz-ийн алгоритмын цаад санаа бол хуваа ба ялагтун юм.

Энэ нь анхны тэмдэгт мөрийг хагасуудад хувааж, хагас бүрд бүхэлдээ орших давталтын тоог хоёр рекурсив дуудалтаар тооцоолно. Дараа нь хэцүү хэсэг ирнэ. Алгоритм эхний хагаст эхэлж, хоёр дахь хагаст дуусах бүх давталтыг олно (эдгээрийг бид огтлолцох давталт гэж нэрлэнэ). Энэ бол Main-Lorentz-ийн алгоритмын үндсэн хэсэг бөгөөд бид үүнийг энд дэлгэрэнгүй хэлэлцэнэ.

Хуваа ба ялагтун алгоритмуудын complexity сайн судлагдсан. Мастер теорем нь хэрэв бид огтлолцох давталтуудыг $O(n)$ хугацаанд тооцоолж чадвал бид $O(n \log n)$ алгоритмтай болно гэж хэлдэг.

Огтлолцох давталтыг хайх

Тэгэхээр бид тэмдэгт мөрийн эхний хагаст (үүнийг $u$ гэж нэрлэе) эхэлж, хоёр дахь хагаст (үүнийг $v$ гэж нэрлэе) дуусах ийм бүх давталтыг олохыг хүсэж байна:

$$s = u + v$$

Тэдгээрийн урт нь $s$-ийн уртыг хоёрт хуваасантай ойролцоогоор тэнцүү.

Дурын давталтыг авч үзээд дундах тэмдэгтийг (тодруулбал давталтын хоёр дахь хагасын эхний тэмдэгтийг) хар. Өөрөөр хэлбэл хэрэв давталт нь $s[i \dots j]$ дэд мөр бол дундах тэмдэгт нь $(i + j + 1) / 2$ юм.

Энэ тэмдэгт аль тэмдэгт мөрд - $u$ тэмдэгт мөрд эсвэл $v$ тэмдэгт мөрд байрлаж байгаагаас хамааран бид давталтыг зүүн эсвэл баруун гэж нэрлэнэ. Өөрөөр хэлбэл тэмдэгт мөрийн ихэнх хэсэг нь $u$-д орших бол түүнийг зүүн гэж нэрлэх ба эс бөгөөс баруун гэж нэрлэнэ.

Одоо бид бүх зүүн давталтыг хэрхэн олохыг хэлэлцэнэ. Бүх баруун давталтыг олохыг мөн ижил аргаар хийж болно.

Зүүн давталтын уртыг $2l$ гэж тэмдэглэе (өөрөөр хэлбэл давталтын хагас бүр $l$ урттай). $v$ тэмдэгт мөрд унах давталтын эхний тэмдэгтийг авч үз (энэ нь $s$ тэмдэгт мөрд $|u|$ байрлалд байна). Энэ нь түүнээс $l$ байрлалын өмнөх тэмдэгттэй давхцана, энэ байрлалыг $cntr$ гэж тэмдэглэе.

Бид энэ $cntr$ байрлалыг тогтоож, энэ $cntr$ байрлал дахь бүх давталтыг хайна.

Жишээ нь:

$$c ~ \underset{cntr}{a} ~ c ~ | ~ a ~ d ~ a$$

Босоо зураас хоёр хагасыг тусгаарлана. Энд бид $cntr = 1$ байрлалыг тогтоосон ба энэ байрлалд бид $caca$ давталтыг олно.

Хэрэв бид $cntr$ байрлалыг тогтоовол боломжит давталтуудын уртыг нэгэн зэрэг тогтоох нь ойлгомжтой: $l = |u| - cntr$. Эдгээр давталтыг хэрхэн олохыг мэдмэгц бид $cntr$-ийн боломжит бүх утгыг $0$-ээс $|u|-1$ хүртэл гүйж, $l = |u|,~ |u|-1,~ \dots, 1$ урттай бүх зүүн огтлолцох давталтыг олно.

Зүүн огтлолцох давталтын шалгуур

Одоо тогтоосон $cntr$-ийн хувьд бид ийм бүх давталтыг хэрхэн олох вэ? Ийм давталт олон байж болохыг санаарай.

Дахин дүрслэлийг харцгаая, энэ удаад $abcabc$ давталтын хувьд:

$$\overbrace{a}^{l_1} ~ \overbrace{\underset{cntr}{b} ~ c}^{l_2} ~ \overbrace{a}^{l_1} ~ | ~ \overbrace{b ~ c}^{l_2}$$

Энд бид давталтын хоёр хэсгийн уртыг $l_1$ ба $l_2$ гэж тэмдэглэсэн: $l_1$ нь $cntr-1$ байрлал хүртэлх давталтын урт, $l_2$ нь $cntr$-ээс давталтын хагасын төгсгөл хүртэлх давталтын урт юм. Давталтын нийт урт болгож бид $2l = l_1 + l_2 + l_1 + l_2$-г авна.

$cntr$ байрлалд $2l = 2(l_1 + l_2) = 2(|u| - cntr)$ урттай ийм давталт байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөлийг гаргая:

  • $cntr$ байрлалын өмнөх эхний $k_1$ тэмдэгт нь $u$ тэмдэгт мөрийн сүүлийн $k_1$ тэмдэгттэй давхцах байх хамгийн том тоо нь $k_1$ байг:
$$ u[cntr - k_1 \dots cntr - 1] = u[|u| - k_1 \dots |u| - 1] $$
  • $cntr$ байрлалаас эхлэх $k_2$ тэмдэгт нь $v$ тэмдэгт мөрийн эхний $k_2$ тэмдэгттэй давхцах байх хамгийн том тоо нь $k_2$ байг:
$$ u[cntr \dots cntr + k_2 - 1] = v[0 \dots k_2 - 1] $$
  • Тэгвэл бид дараах нөхцөлтэй дурын $(l_1,~ l_2)$ хосын хувьд яг давталттай болно
$$ \begin{align} l_1 &\le k_1, \\\\ l_2 &\le k_2. \\\\ \end{align} $$

Дүгнэвэл:

  • Бид тодорхой $cntr$ байрлалыг тогтооно.
  • Бидний одоо олох бүх давталт $2l = 2(|u| - cntr)$ урттай байна. Ийм давталт олон байж болох ба тэдгээр нь $l_1$ ба $l_2 = l - l_1$ уртаас хамаарна.
  • Бид дээр тайлбарласны дагуу $k_1$ ба $k_2$-г олно.
  • Тэгвэл тохирох бүх давталт нь хэсгүүдийн урт $l_1$ ба $l_2$ нь дараах нөхцөлийг хангах давталтууд юм:
$$ \begin{align} l_1 + l_2 &= l = |u| - cntr \\\\ l_1 &\le k_1, \\\\ l_2 &\le k_2. \\\\ \end{align} $$

Тиймээс үлдсэн ганц хэсэг бол бид $cntr$ байрлал бүрийн хувьд $k_1$ ба $k_2$ утгыг хэрхэн хурдан тооцоолох вэ гэдэг юм. Аз болоход бид тэдгээрийг Z-функц ашиглан $O(1)$-д тооцоолж чадна:

  • $\overline{u}$ тэмдэгт мөрийн (өөрөөр хэлбэл урвуулсан $u$ тэмдэгт мөрийн) Z-функцийг тооцоолох замаар байрлал бүрийн $k_1$ утгыг олж болно. Тэгвэл тодорхой $cntr$-ийн $k_1$ утга нь Z-функцийн массивын харгалзах утгатай тэнцүү байна.
  • Бүх $k_2$ утгыг урьдчилан тооцоолохын тулд бид $v + \# + u$ тэмдэгт мөрийн (өөрөөр хэлбэл $\#$ тусгаарлагч тэмдэгт ба $v$ тэмдэгт мөртэй залгасан $u$ тэмдэгт мөрийн) Z-функцийг тооцоолно. Дахин бид $k_2$ утгыг авахын тулд Z-функц дэх харгалзах утгыг хайж олоход л хангалттай.

Тиймээс энэ нь бүх зүүн огтлолцох давталтыг олоход хангалттай.

Баруун огтлолцох давталт

Баруун огтлолцох давталтыг тооцоолохдоо бид ижил төстэйгээр үйлдэнэ: бид $cntr$ төвийг $u$ тэмдэгт мөрийн сүүлийн тэмдэгтэд харгалзах тэмдэгт гэж тодорхойлно.

Тэгвэл $k_1$ урт нь $u$ тэмдэгт мөрийн сүүлийн тэмдэгтүүдтэй давхцах, $cntr$ байрлалын өмнөх (түүнийг оруулаад) тэмдэгтийн хамгийн их тоо гэж тодорхойлогдоно. $k_2$ урт нь $v$ тэмдэгт мөрийн тэмдэгтүүдтэй давхцах, $cntr + 1$-ээс эхлэх тэмдэгтийн хамгийн их тоо гэж тодорхойлогдоно.

Ингэснээр бид $\overline{u} + \# + \overline{v}$ ба $v$ тэмдэгт мөрүүдийн Z-функцийг тооцоолох замаар $k_1$ ба $k_2$ утгыг олж чадна.

Үүний дараа бид бүх $cntr$ байрлалыг харж, зүүн огтлолцох давталтад ашигласантай ижил шалгуурыг ашиглан давталтуудыг олж чадна.

Implementation

The implementation of the Main-Lorentz algorithm finds all repetitions in form of peculiar tuples of size four: $(cntr,~ l,~ k_1,~ k_2)$ in $O(n \log n)$ time. If you only want to find the number of repetitions in a string, or only want to find the longest repetition in a string, this information is enough and the runtime will still be $O(n \log n)$.

Notice that if you want to expand these tuples to get the starting and end position of each repetition, then the runtime will be the runtime will be $O(n^2)$ (remember that there can be $O(n^2)$ repetitions). In this implementation we will do so, and store all found repetition in a vector of pairs of start and end indices.

vector<int> z_function(string const& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r)
            z[i] = min(r-i+1, z[i-l]);
        while (i + z[i] < n && s[z[i]] == s[i+z[i]])
            z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int get_z(vector<int> const& z, int i) {
    if (0 <= i && i < (int)z.size())
        return z[i];
    else
        return 0;
}

vector<pair<int, int>> repetitions;

void convert_to_repetitions(int shift, bool left, int cntr, int l, int k1, int k2) {
    for (int l1 = max(1, l - k2); l1 <= min(l, k1); l1++) {
        if (left && l1 == l) break;
        int l2 = l - l1;
        int pos = shift + (left ? cntr - l1 : cntr - l - l1 + 1);
        repetitions.emplace_back(pos, pos + 2*l - 1);
    }
}

void find_repetitions(string s, int shift = 0) {
    int n = s.size();
    if (n == 1)
        return;

    int nu = n / 2;
    int nv = n - nu;
    string u = s.substr(0, nu);
    string v = s.substr(nu);
    string ru(u.rbegin(), u.rend());
    string rv(v.rbegin(), v.rend());

    find_repetitions(u, shift);
    find_repetitions(v, shift + nu);

    vector<int> z1 = z_function(ru);
    vector<int> z2 = z_function(v + '#' + u);
    vector<int> z3 = z_function(ru + '#' + rv);
    vector<int> z4 = z_function(v);

    for (int cntr = 0; cntr < n; cntr++) {
        int l, k1, k2;
        if (cntr < nu) {
            l = nu - cntr;
            k1 = get_z(z1, nu - cntr);
            k2 = get_z(z2, nv + 1 + cntr);
        } else {
            l = cntr - nu + 1;
            k1 = get_z(z3, nu + 1 + nv - 1 - (cntr - nu));
            k2 = get_z(z4, (cntr - nu) + 1);
        }
        if (k1 + k2 >= l)
            convert_to_repetitions(shift, cntr < nu, cntr, l, k1, k2);
    }
}