Угтвар функц. Кнут–Моррис–Праттын алгоритм¶

Угтвар функцийн тодорхойлолт¶

Танд $n$ урттай $s$ тэмдэгт мөр өгөгдсөн. Энэ тэмдэгт мөрийн угтвар функц нь $n$ урттай $\pi$ массив гэж тодорхойлогдох ба $\pi[i]$ нь $s[0 \dots i]$ дэд мөрийн мөн энэ дэд мөрийн дагавар байх хамгийн урт жинхэнэ угтварын урт юм. Тэмдэгт мөрийн жинхэнэ угтвар гэдэг нь тэмдэгт мөртэй өөртэй нь тэнцүү биш угтвар юм. Тодорхойлолтоор $\pi[0] = 0$.

Математикаар угтвар функцийн тодорхойлолтыг дараах байдлаар бичиж болно:

$$\pi[i] = \max_ {k = 0 \dots i} \{k : s[0 \dots k-1] = s[i-(k-1) \dots i] \}$$

Жишээ нь "abcabcd" тэмдэгт мөрийн угтвар функц нь $[0, 0, 0, 1, 2, 3, 0]$, "aabaaab" тэмдэгт мөрийн угтвар функц нь $[0, 1, 0, 1, 2, 2, 3]$ юм.

Тривиаль алгоритм¶

Угтвар функцийн тодорхойлолтыг яг дагадаг алгоритм нь дараах юм:

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 0; i < n; i++)
        for (int k = 0; k <= i; k++)
            if (s.substr(0, k) == s.substr(i-k+1, k))
                pi[i] = k;
    return pi;
}

Түүний complexity нь $O(n^3)$ бөгөөд сайжруулах боломжтой болохыг харахад амархан.

Үр ашигтай алгоритм¶

Энэ алгоритмыг Кнут, Пратт нар, мөн тэднээс үл хамааран Моррис 1977 онд санал болгосон. Үүнийг дэд мөр хайх алгоритмын үндсэн функц болгон ашигласан.

Эхний оновчлол¶

Эхний чухал ажиглалт нь угтвар функцийн утга хамгийн ихдээ нэгээр л нэмэгдэж чадна гэдэг явдал юм.

Үнэхээр эс бөгөөс хэрэв $\pi[i + 1] \gt \pi[i] + 1$ бол бид $i + 1$ байрлалд дуусах, $\pi[i + 1]$ урттай энэ дагаврыг аваад түүнээс сүүлийн тэмдэгтийг хасаж болно. Бид $i$ байрлалд дуусах, $\pi[i + 1] - 1$ урттай дагавартай болох ба энэ нь $\pi[i]$-ээс сайн, өөрөөр хэлбэл бид зөрчилд хүрнэ.

Дараах дүрслэл энэ зөрчлийг харуулна. $i$ байрлал дахь мөн угтвар байх хамгийн урт жинхэнэ дагавар нь $2$ урттай, харин $i+1$ байрлалд $4$ урттай байна. Тиймээс $s_0 ~ s_1 ~ s_2 ~ s_3$ тэмдэгт мөр нь $s_{i-2} ~ s_{i-1} ~ s_i ~ s_{i+1}$ тэмдэгт мөртэй тэнцүү бөгөөд энэ нь $s_0 ~ s_1 ~ s_2$ ба $s_{i-2} ~ s_{i-1} ~ s_i$ тэмдэгт мөрүүд мөн тэнцүү гэсэн үг тул $\pi[i]$ нь $3$ байх ёстой.

$$\underbrace{\overbrace{s_0 ~ s_1}^{\pi[i] = 2} ~ s_2 ~ s_3}_{\pi[i+1] = 4} ~ \dots ~ \underbrace{s_{i-2} ~ \overbrace{s_{i-1} ~ s_{i}}^{\pi[i] = 2} ~ s_{i+1}}_{\pi[i+1] = 4}$$

Тиймээс дараагийн байрлал руу шилжихэд угтвар функцийн утга нэгээр нэмэгдэх, хэвээр байх, эсвэл ямар нэг хэмжээгээр багасах боломжтой. Энэ баримт нь алгоритмын complexity-г $O(n^2)$ болгон бууруулах боломжийг аль хэдийн олгож байна, учир нь нэг алхамд угтвар функц хамгийн ихдээ нэгээр өсч чадна. Нийтдээ функц хамгийн ихдээ $n$ алхам өсч чадах тул нийтдээ ердөө $n$ алхам багасч чадна. Энэ нь бид ердөө $O(n)$ тэмдэгт мөрийн харьцуулалт хийж, $O(n^2)$ complexity-д хүрэх ёстой гэсэн үг юм.

Хоёр дахь оновчлол¶

Цааш явцгаая, бид тэмдэгт мөрийн харьцуулалтаас салахыг хүсэж байна. Үүнийг гүйцэтгэхийн тулд бид өмнөх алхмуудад тооцоолсон бүх мэдээллийг ашиглах ёстой.

Тэгэхээр $i + 1$-ийн хувьд угтвар функц $\pi$-ийн утгыг тооцоолъё. Хэрэв $s[i+1] = s[\pi[i]]$ бол бид $\pi[i+1] = \pi[i] + 1$ гэж итгэлтэйгээр хэлж чадна, учир нь $i$ байрлал дахь $\pi[i]$ урттай дагавар нь $\pi[i]$ урттай угтвартай тэнцүү болохыг бид аль хэдийн мэднэ. Үүнийг дахин жишээгээр дүрслэв.

$$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i]} ~ \overbrace{s_3}^{s_3 = s_{i+1}}}_{\pi[i+1] = \pi[i] + 1} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{\pi[i]} ~ \overbrace{s_{i+1}}^{s_3 = s_{i + 1}}}_{\pi[i+1] = \pi[i] + 1}$$

Хэрэв ийм биш буюу $s[i+1] \neq s[\pi[i]]$ бол бид илүү богино тэмдэгт мөр оролдох хэрэгтэй. Ажлыг хурдасгахын тулд бид $i$ байрлал дахь угтварын шинж чанар биелэх буюу $s[0 \dots j-1] = s[i-j+1 \dots i]$ байх хамгийн урт $j \lt \pi[i]$ урт руу шууд шилжихийг хүсэж байна:

$$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1}$$

Үнэхээр хэрэв бид ийм $j$ урт олбол дахин зөвхөн $s[i+1]$ ба $s[j]$ тэмдэгтүүдийг харьцуулахад л хангалттай. Хэрэв тэдгээр тэнцүү бол бид $\pi[i+1] = j + 1$ гэж оноож болно. Эс бөгөөс бид угтварын шинж чанар биелэх, $j$-ээс бага хамгийн том утгыг олох хэрэгтэй болно гэх мэтчилэн үргэлжилнэ. Энэ нь $j = 0$ хүртэл үргэлжилж болно. Хэрэв тэгвэл $s[i+1] = s[0]$ бол бид $\pi[i+1] = 1$ гэж оноох ба эс бөгөөс $\pi[i+1] = 0$ гэж ононо.

Тэгэхээр бидэнд алгоритмын ерөнхий схем аль хэдийн бий. Үлдсэн ганц асуулт бол бид $j$-ийн уртыг хэрхэн үр дүнтэй олох вэ гэдэг юм. Дүгнэвэл: угтварын шинж чанар биелэх буюу $s[0 \dots j-1] = s[i-j+1 \dots i]$ байх $i$ байрлал дахь одоогийн $j$ уртын хувьд бид угтварын шинж чанар биелэх хамгийн том $k \lt j$-г олохыг хүсэж байна.

$$\overbrace{\underbrace{s_0 ~ s_1}_k ~ s_2 ~ s_3}^j ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_k}^j ~s_{i+1}$$

Дүрслэл нь энэ нь бидний өмнө нь аль хэдийн тооцоолсон $\pi[j-1]$-ийн утга байх ёстойг харуулж байна.

Эцсийн алгоритм¶

Тэгэхээр бид эцэст нь ямар ч тэмдэгт мөрийн харьцуулалт хийдэггүй, ердөө $O(n)$ үйлдэл гүйцэтгэдэг алгоритм байгуулж чадна.

Эцсийн процедур энд байна:

Бид угтварын утга $\pi[i]$-г $i = 1$-ээс $i = n-1$ хүртэл гүйх давталтаар тооцоолно ($\pi[0]$-д зүгээр л $0$ оноогдоно).
Одоогийн утга $\pi[i]$-г тооцоолохын тулд бид $i-1$-ийн хамгийн сайн дагаврын уртыг тэмдэглэх $j$ хувьсагчийг тохируулна. Эхэндээ $j = \pi[i-1]$.
$s[j]$ ба $s[i]$-г харьцуулах замаар $j+1$ урттай дагавар мөн угтвар мөн эсэхийг шалга. Хэрэв тэдгээр тэнцүү бол бид $\pi[i] = j + 1$ гэж оноох ба эс бөгөөс $j$-г $\pi[j-1]$ болгон багасгаж энэ алхмыг давтана.
Хэрэв бид $j = 0$ урт хүрсэн боловч таарц олдоогүй хэвээр байвал бид $\pi[i] = 0$ гэж оноож, дараагийн $i + 1$ индекс рүү шилжинэ.

Implementation¶

The implementation ends up being surprisingly short and expressive.

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

Энэ бол онлайн алгоритм юм, өөрөөр хэлбэл энэ нь өгөгдлийг ирэх явцад нь боловсруулна — жишээ нь та тэмдэгт мөрийн тэмдэгтүүдийг нэг нэгээр нь уншиж, шууд боловсруулан, дараагийн тэмдэгт бүрийн угтвар функцийн утгыг олж болно. Алгоритм нь тэмдэгт мөрийг өөрийг нь ба өмнө тооцоолсон угтвар функцийн утгуудыг хадгалахыг шаардсаар байх ч хэрэв бид угтвар функц тэмдэгт мөрд авч болох хамгийн их утга $M$-г урьдчилан мэдэж байвал бид тэмдэгт мөрийн эхний $M+1$ тэмдэгт ба угтвар функцийн ижил тооны утгыг л хадгалж болно.

Хэрэглээ¶

Тэмдэгт мөрөөс дэд мөр хайх. Кнут-Моррис-Праттын алгоритм¶

Энэ бодлого бол угтвар функцийн сонгодог хэрэглээ юм.

$t$ текст ба $s$ тэмдэгт мөр өгөгдсөн үед бид $t$ текст дэх $s$ тэмдэгт мөрийн бүх орцын байрлалыг олж харуулахыг хүсэж байна.

Тохиромжтой байдлын үүднээс бид $s$ тэмдэгт мөрийн уртыг $n$, $t$ текстийн уртыг $m$ гэж тэмдэглэнэ.

Бид $s + \# + t$ тэмдэгт мөрийг үүсгэнэ, энд $\#$ нь $s$-д ч, $t$-д ч гарч ирдэггүй тусгаарлагч юм. Энэ тэмдэгт мөрийн угтвар функцийг тооцоолъё. Одоо эхний $n + 1$ гишүүнээс ($s$ тэмдэгт мөр ба тусгаарлагчид харьяалагдах) бусад угтвар функцийн утгуудын утга учрын тухай бодъё. Тодорхойлолтоор $\pi[i]$ утга нь $i$ байрлалд дуусах, угтвартай давхцах дэд мөрийн хамгийн урт уртыг харуулна. Гэвч бидний тохиолдолд энэ нь $s$-тэй давхцах ба $i$ байрлалд дуусах хамгийн том блокоос өөр зүйл биш юм. Тусгаарлагчаас болж энэ урт $n$-ээс их байж чадахгүй. Гэвч хэрэв $\pi[i] = n$ тэнцэтгэлд хүрвэл энэ нь $s$ тэмдэгт мөр энэ байрлалд бүрэн гарч ирнэ буюу $i$ байрлалд дуусна гэсэн үг юм. Байрлалууд нь $s + \# + t$ тэмдэгт мөрд индексжсэн болохыг зүгээр л бүү мартаарай.

Тиймээс хэрэв ямар нэг $i$ байрлалд $\pi[i] = n$ байвал $t$ тэмдэгт мөрийн $i - (n + 1) - n + 1 = i - 2n$ байрлалд $s$ тэмдэгт мөр гарч ирнэ.

Угтвар функцийн тооцооллын тайлбарт аль хэдийн дурдсанчлан хэрэв угтварын утга тодорхой утгаас хэзээ ч хэтрэхгүйг бид мэдэж байвал бид бүхэл тэмдэгт мөр ба бүхэл функцийг хадгалах шаардлагагүй, зөвхөн түүний эхлэлийг хадгалахад хангалттай. Бидний тохиолдолд энэ нь бид зөвхөн $s + \#$ тэмдэгт мөр ба түүний угтвар функцийн утгуудыг хадгалахад хангалттай гэсэн үг юм. Бид $t$ тэмдэгт мөрийн тэмдэгтийг нэг нэгээр нь уншиж, угтвар функцийн одоогийн утгыг тооцоолж болно.

Ингэснээр Кнут-Моррис-Праттын алгоритм бодлогыг $O(n + m)$ хугацаа, $O(n)$ санах ойд бодно.

Угтвар бүрийн орцын тоог тоолох¶

Энд бид хоёр бодлогыг нэг дор хэлэлцэнэ. $n$ урттай $s$ тэмдэгт мөр өгөгдсөн. Бодлогын эхний хувилбарт бид угтвар $s[0 \dots i]$ бүр мөн тэр тэмдэгт мөрд хэдэн удаа гарч ирэхийг тоолохыг хүсэж байна. Бодлогын хоёр дахь хувилбарт өөр $t$ тэмдэгт мөр өгөгдсөн ба бид угтвар $s[0 \dots i]$ бүр $t$-д хэдэн удаа гарч ирэхийг тоолохыг хүсэж байна.

Эхлээд бид эхний бодлогыг бодно. $i$ байрлал дахь угтвар функц $\pi[i]$-ийн утгыг авч үз. Тодорхойлолтоор энэ нь $s$ тэмдэгт мөрийн $\pi[i]$ урттай угтвар $i$ байрлалд гарч ирж дуусна гэсэн үг бөгөөд энэ тодорхойлолтыг дагах илүү урт угтвар байхгүй. Үүний зэрэгцээ илүү богино угтварууд энэ байрлалд дуусч болно. Бид угтвар функцийг өөрийг нь тооцоолохдоо аль хэдийн хариулсан ижил асуулттай тулгарч байгааг харахад хэцүү биш: $i$ байрлалд дуусах дагавар байх $j$ урттай угтвар өгөгдсөн үед мөн $i$ байрлалд дуусах дагавар байх дараагийн бага $\lt j$ угтвар юу вэ. Тиймээс $i$ байрлалд $\pi[i]$ урттай угтвар, $\pi[\pi[i] - 1]$ урттай угтвар, $\pi[\pi[\pi[i] - 1] - 1]$ угтвар гэх мэтчилэн индекс тэг болтол дуусна. Ингэснээр бид хариуг дараах байдлаар тооцоолж болно.

vector<int> ans(n + 1);
for (int i = 0; i < n; i++)
    ans[pi[i]]++;
for (int i = n-1; i > 0; i--)
    ans[pi[i-1]] += ans[i];
for (int i = 0; i <= n; i++)
    ans[i]++;

Here for each value of the prefix function we first count how many times it occurs in the array $\pi$, and then compute the final answers: if we know that the length prefix $i$ appears exactly $\text{ans}[i]$ times, then this number must be added to the number of occurrences of its longest suffix that is also a prefix. At the end we need to add $1$ to each result, since we also need to count the original prefixes also.

Одоо хоёр дахь бодлогыг авч үзье. Бид Кнут-Моррис-Праттын заль мэхийг хэрэглэнэ: бид $s + \# + t$ тэмдэгт мөрийг үүсгэж, түүний угтвар функцийг тооцоолно. Эхний бодлогоос ялгаатай зүйл нь бид зөвхөн $t$ тэмдэгт мөрд хамаарах угтварын утгууд буюу $i \ge n + 1$-ийн хувьд $\pi[i]$-г сонирхож байна. Эдгээр утгаар бид эхний бодлого дахьтай яг ижил тооцооллыг гүйцэтгэж болно.

Тэмдэгт мөр дэх ялгаатай дэд мөрийн тоо¶

$n$ урттай $s$ тэмдэгт мөр өгөгдсөн. Бид түүнд гарч ирэх ялгаатай дэд мөрийн тоог тооцоолохыг хүсэж байна.

Бид энэ бодлогыг давталттайгаар бодно. Тухайлбал ялгаатай дэд мөрийн одоогийн тоог мэдэж байгаад төгсгөлд нь тэмдэгт нэмэх замаар энэ тоог хэрхэн дахин тооцоолохыг бид сурна.

Тэгэхээр $k$ нь $s$ дэх ялгаатай дэд мөрийн одоогийн тоо байг, бид $s$-ийн төгсгөлд $c$ тэмдэгтийг нэмнэ. $c$-ээр төгсөх зарим шинэ дэд мөр гарч ирэх нь илэрхий. Бид өмнө нь гарч ирээгүй байсан эдгээр шинэ дэд мөрийг тоолохыг хүсэж байна.

Бид $t = s + c$ тэмдэгт мөрийг аваад түүнийг урвуулна. Одоо бодлого өөр хаана ч гарч ирэхгүй хэдэн угтвар байгааг тооцоолох болж хувирлаа. Хэрэв бид урвуулсан $t$ тэмдэгт мөрийн угтвар функцийн хамгийн их утга $\pi_{\text{max}}$-г тооцоолбол $s$-д гарч ирэх хамгийн урт угтвар нь $\pi_{\text{max}}$ урттай байна. Бага урттай бүх угтвар мөн түүнд гарч ирэх нь ойлгомжтой.

Тиймээс бид шинэ тэмдэгт $c$ нэмэх үед гарч ирэх шинэ дэд мөрийн тоо нь $|s| + 1 - \pi_{\text{max}}$ юм.

Тиймээс залгасан тэмдэгт бүрийн хувьд бид шинэ дэд мөрийн тоог $O(n)$ хугацаанд тооцоолж чадах ба энэ нь нийтдээ $O(n^2)$ time complexity өгнө.

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

Тэмдэгт мөр шахах¶

$n$ урттай $s$ тэмдэгт мөр өгөгдсөн. Бид тэмдэгт мөрийн хамгийн богино "шахсан" илэрхийллийг олохыг хүсэж байна, өөрөөр хэлбэл $s$-г $t$-ийн нэг буюу хэд хэдэн хуулбарын залгалт хэлбэрээр илэрхийлж болохоор хамгийн бага урттай $t$ тэмдэгт мөрийг олохыг хүсэж байна.

Бид зөвхөн $t$-ийн уртыг олоход хангалттай нь ойлгомжтой. Уртыг мэдсэнээр бодлогын хариу нь энэ урттай $s$-ийн угтвар байх болно.

$s$-ийн угтвар функцийг тооцоолъё. Түүний сүүлийн утгыг ашиглан бид $k = n - \pi[n - 1]$ утгыг тодорхойлно. Хэрэв $k$ нь $n$-г хуваавал $k$ нь хариу байх ба эс бөгөөс үр дүнтэй шахалт байхгүй бөгөөд хариу нь $n$ болохыг бид үзүүлнэ.

$n$ нь $k$-д хуваагдана гэж үзье. Тэгвэл тэмдэгт мөрийг $k$ урттай блокуудад хувааж болно. Угтвар функцийн тодорхойлолтоор $n - k$ урттай угтвар нь өөрийн дагавартай тэнцүү байна. Гэвч энэ нь сүүлийн блок өмнөх блоктой тэнцүү гэсэн үг юм. Өмнөх блок нь түүний өмнөх блоктой тэнцүү байх ёстой. Гэх мэтчилэн үргэлжилнэ. Үр дүнд нь бүх блок тэнцүү болох нь тогтоогддог тул бид $s$ тэмдэгт мөрийг $k$ урт хүртэл шахаж болно.

Мэдээж бид энэ нь үнэхээр оптимум болохыг үзүүлэх шаардлагатай хэвээр байна. Үнэхээр хэрэв $k$-ээс бага шахалт байсан бол төгсгөл дэх угтвар функц $n - k$-ээс их байх байсан. Тиймээс $k$ үнэхээр хариу мөн.

Одоо $n$ нь $k$-д хуваагдахгүй гэж үзье. Энэ нь хариуны урт $n$ байна гэсэн үг болохыг бид үзүүлнэ. Бид үүнийг зөрчлөөр батална. Хариу оршин байна, шахалт нь $p$ урттай ($p$ нь $n$-г хуваана) гэж үзье. Тэгвэл угтвар функцийн сүүлийн утга $n - p$-ээс их байх ёстой, өөрөөр хэлбэл дагавар эхний блокийг хэсэгчлэн бүрхэнэ. Одоо тэмдэгт мөрийн хоёр дахь блокийг авч үз. Угтвар нь дагавартай тэнцүү бөгөөд угтвар, дагавар хоёулаа энэ блокийг бүрхэх ба тэдгээрийн бие биетэйгээ харьцангуй шилжилт $k$ нь блокийн урт $p$-г хуваахгүй тул (эс бөгөөс $k$ нь $n$-г хуваана) блокийн бүх тэмдэгт ижил байх ёстой. Гэвч тэгвэл тэмдэгт мөр ердөө нэг тэмдэгтийг дахин дахин давтсанаас бүрдэх тул бид түүнийг $1$ хэмжээтэй тэмдэгт мөр болгон шахаж болох ба энэ нь $k = 1$ өгөх бөгөөд $k$ нь $n$-г хуваана. Зөрчил.

$$\overbrace{s_0 ~ s_1 ~ s_2 ~ s_3}^p ~ \overbrace{s_4 ~ s_5 ~ s_6 ~ s_7}^p$$

$$s_0 ~ s_1 ~ s_2 ~ \underbrace{\overbrace{s_3 ~ s_4 ~ s_5 ~ s_6}^p ~ s_7}_{\pi[7] = 5}$$

$$s_4 = s_3, ~ s_5 = s_4, ~ s_6 = s_5, ~ s_7 = s_6 ~ \Rightarrow ~ s_0 = s_1 = s_2 = s_3$$

Угтвар функцээр автомат байгуулах¶

Тусгаарлагчаар холбосон хоёр тэмдэгт мөрийн залгалт руу буцаж орцгооё, өөрөөр хэлбэл $s$ ба $t$ тэмдэгт мөрүүдийн хувьд бид $s + \# + t$ тэмдэгт мөрийн угтвар функцийг тооцоолно. $\#$ нь тусгаарлагч тул угтвар функцийн утга $|s|$-ээс хэзээ ч хэтрэхгүй нь илэрхий. Эндээс зөвхөн $s + \#$ тэмдэгт мөр ба түүний угтвар функцийн утгуудыг хадгалахад хангалттай бөгөөд бид дараагийн бүх тэмдэгтийн угтвар функцийг явцын дунд тооцоолж чадна гэж гарна:

$$\underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ \#}_{\text{need to store}} ~ \underbrace{t_0 ~ t_1 ~ \dots ~ t_{m-1}}_{\text{do not need to store}}$$

Үнэхээр ийм нөхцөлд дараагийн тэмдэгт $c \in t$ ба өмнөх байрлалын угтвар функцийн утгыг мэдэх нь $t$ тэмдэгт мөрийн өмнөх ямар ч тэмдэгт, тэдгээр дэх угтвар функцийн утгыг ашиглалгүйгээр угтвар функцийн дараагийн утгыг тооцоолоход хангалттай мэдээлэл юм.

Өөрөөр хэлбэл бид автомат (төгсгөлөг төлөвт машин) байгуулж чадна: түүн дэх төлөв нь угтвар функцийн одоогийн утга бөгөөд нэг төлвөөс нөгөө рүү шилжих шилжилт нь дараагийн тэмдэгтээр гүйцэтгэгдэнэ.

Ингэснээр $t$ тэмдэгт мөргүйгээр ч бид шилжилтийн хүснэгт тооцоолохтой ижил алгоритм ашиглан ийм $(\text{old}_\pi, c) \rightarrow \text{new}_\pi$ шилжилтийн хүснэгтийг байгуулж чадна:

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            int j = i;
            while (j > 0 && 'a' + c != s[j])
                j = pi[j-1];
            if ('a' + c == s[j])
                j++;
            aut[i][c] = j;
        }
    }
}

Гэвч энэ хэлбэрээр алгоритм цагаан толгойн жижиг үсгийн хувьд $O(n^2 26)$ хугацаанд ажиллана. Бид динамик программчлал хэрэглэж, хүснэгтийн аль хэдийн тооцоолсон хэсгүүдийг ашиглаж болохыг анзаар. Бид $j$ утгаас $\pi[j-1]$ утга руу шилжих бүрд үнэндээ $(j, c)$ шилжилт нь $(\pi[j-1], c)$ шилжилттэй ижил төлөв рүү хөтөлнө гэсэн үг бөгөөд энэ хариу аль хэдийн нарийн тооцоологдсон байдаг.

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            if (i > 0 && 'a' + c != s[i])
                aut[i][c] = aut[pi[i-1]][c];
            else
                aut[i][c] = i + ('a' + c == s[i]);
        }
    }
}

Үр дүнд нь бид автоматыг $O(26 n)$ хугацаанд байгуулна.

Ийм автомат хэзээ хэрэгтэй вэ? Эхлээд бид $s + \# + t$ тэмдэгт мөрийн угтвар функц ба түүний утгуудыг голчлон нэг зорилгоор ашигладгийг сана: $t$ тэмдэгт мөр дэх $s$ тэмдэгт мөрийн бүх орцыг олох.

Тиймээс энэ автоматын хамгийн илэрхий ашиг тус нь $s + \# + t$ тэмдэгт мөрийн угтвар функцийн тооцооллыг хурдасгах явдал юм. $s + \#$-ийн автоматыг байгуулснаар бид $s$ тэмдэгт мөр буюу түүн дэх угтвар функцийн утгуудыг хадгалах шаардлагагүй болно. Бүх шилжилт хүснэгтэд аль хэдийн тооцоологдсон байна.

Гэвч хоёр дахь, тийм ч илэрхий бус хэрэглээ бий. Бид $t$ тэмдэгт мөр нь ямар нэг дүрмээр байгуулагдсан асар том тэмдэгт мөр байх үед автоматыг ашиглаж болно. Энэ нь жишээ нь Грэйгийн тэмдэгт мөр, эсвэл оролтын хэд хэдэн богино тэмдэгт мөрийн рекурсив хослолоор үүссэн тэмдэгт мөр байж болно.

Бүрэн байх үүднээс бид ийм бодлого бодно: $k \le 10^5$ тоо ба $\le 10^5$ урттай $s$ тэмдэгт мөр өгөгдсөн. Бид $k$ дахь Грэйгийн тэмдэгт мөр дэх $s$-ийн орцын тоог тооцоолох ёстой. Грэйгийн тэмдэгт мөрүүд дараах байдлаар тодорхойлогддогийг сана:

$$\begin{align} g_1 &= \text{"a"}\\ g_2 &= \text{"aba"}\\ g_3 &= \text{"abacaba"}\\ g_4 &= \text{"abacabadabacaba"} \end{align}$$

Ийм тохиолдолд одон орны хэмжээний урттай учраас $t$ тэмдэгт мөрийг байгуулах нь ч боломжгүй байх болно. $k$ дахь Грэйгийн тэмдэгт мөр $2^k-1$ тэмдэгтийн урттай. Гэвч бид зөвхөн эхлэл дэх угтвар функцийн утгыг мэдсэнээр тэмдэгт мөрийн төгсгөл дэх угтвар функцийн утгыг үр дүнтэй тооцоолж чадна.

Автоматаас гадна бид $G[i][j]$ утгыг мөн тооцоолно — $j$ төлвөөс эхлэн $g_i$ тэмдэгт мөрийг боловсруулсны дараах автоматын утга. Түүнчлэн бид $K[i][j]$ утгыг тооцоолно — $j$ төлвөөс эхлэн $g_i$-г боловсруулах явцад $g_i$ дэх $s$-ийн орцын тоо. Үнэндээ $K[i][j]$ нь үйлдлүүдийг гүйцэтгэх явцад угтвар функц $|s|$ утгыг хэдэн удаа авсан тоо юм. Тэгвэл бодлогын хариу нь $K[k][0]$ байх болно.

Бид эдгээр утгыг хэрхэн тооцоолох вэ? Эхлээд суурь утгууд нь $G[0][j] = j$ ба $K[0][j] = 0$ юм. Дараагийн бүх утгыг өмнөх утгууд ба автоматыг ашиглан тооцоолж болно. Ямар нэг $i$-ийн утгыг тооцоолохын тулд бид $g_i$ тэмдэгт мөр нь $g_{i-1}$, цагаан толгойн $i$ дахь тэмдэгт, ба $g_{i-1}$-ээс бүрдэхийг сана. Ингэснээр автомат дараах төлөв рүү орно:

$$\text{mid} = \text{aut}[G[i-1][j]][i]$$

$$G[i][j] = G[i-1][\text{mid}]$$

$K[i][j]$-ийн утгыг мөн амархан тоолж болно.

$$K[i][j] = K[i-1][j] + (\text{mid} == |s|) + K[i-1][\text{mid}]$$

Тиймээс бид Грэйгийн тэмдэгт мөрийн бодлогыг, мөн үүнтэй адил бусад олон тооны ижил төстэй бодлогыг бодож чадна. Жишээ нь яг ижил арга дараах бодлогыг мөн бодно: бидэнд $s$ тэмдэгт мөр ба зарим $t_i$ хэв маяг өгөгдсөн, тэдгээр тус бүр дараах байдлаар заагдсан: энэ нь ердийн тэмдэгтүүдийн тэмдэгт мөр бөгөөд $t_k^{\text{cnt}}$ хэлбэрийн өмнөх тэмдэгт мөрүүдийн зарим рекурсив оруулга байж болно, энэ нь энэ байранд бид $t_k$ тэмдэгт мөрийг $\text{cnt}$ удаа оруулах ёстой гэсэн үг юм. Ийм хэв маягийн жишээ:

$$\begin{align} t_1 &= \text{"abdeca"}\\ t_2 &= \text{"abc"} + t_1^{30} + \text{"abd"}\\ t_3 &= t_2^{50} + t_1^{100}\\ t_4 &= t_2^{10} + t_3^{100} \end{align}$$

Рекурсив орлуулга нь тэмдэгт мөрийг хэт томруулж, тэдгээрийн урт $100^{100}$-ийн эрэмбэд хүрч болно.

Бид тэмдэгт мөр бүрд $s$ тэмдэгт мөр хэдэн удаа гарч ирэхийг олох ёстой.

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