Линдоны задаргаа¶
Линдоны задаргаа¶
Эхлээд Линдоны задаргааны ойлголтыг тодорхойлъё.
Тэмдэгт мөрийг өөрийнх нь дурын тривиаль бус дагавараас чанд бага бол энгийн (эсвэл Линдоны үг) гэж нэрлэнэ. Энгийн мөрийн жишээ: $a$, $b$, $ab$, $aab$, $abb$, $ababb$, $abcd$. Тэмдэгт мөр энгийн байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь түүний бүх тривиаль бус циклик шилжилтээс чанд бага байх явдал болохыг үзүүлж болно.
Дараа нь $s$ тэмдэгт мөр өгөгдсөн байг. $s$ тэмдэгт мөрийн Линдоны задаргаа гэдэг нь $s = w_1 w_2 \dots w_k$ задаргаа бөгөөд бүх $w_i$ мөрүүд энгийн байх ба тэдгээр нь өсөхгүй дарааллаар $w_1 \ge w_2 \ge \dots \ge w_k$ байрлана.
Дурын тэмдэгт мөрийн хувьд ийм задаргаа оршин байх ба цор ганц болохыг үзүүлж болно.
Дювалын алгоритм¶
Дювалын алгоритм нь Линдоны задаргааг $O(n)$ хугацаанд, $O(1)$ нэмэлт санах ой ашиглан байгуулна.
Эхлээд өөр нэг ойлголтыг танилцуулъя: $t$ тэмдэгт мөрийг $t = w w \dots w \overline{w}$ хэлбэртэй бол урьд-энгийн гэж нэрлэнэ, энд $w$ нь энгийн мөр, $\overline{w}$ нь $w$-ийн угтвар (хоосон байж болно). Энгийн мөр нь мөн урьд-энгийн юм.
Дювалын алгоритм нь greedy algorithm юм. Гүйцэтгэлийн явцын дурын мөчид $s$ тэмдэгт мөр үнэндээ $s = s_1 s_2 s_3$ гэсэн гурван мөрд хуваагдана, энд $s_1$-ийн Линдоны задаргаа аль хэдийн олдож эцэслэгдсэн, $s_2$ мөр нь урьд-энгийн (мөн бид түүн доторх энгийн мөрийн уртыг мэднэ), $s_3$ нь огт хөндөгдөөгүй байна. Давталт бүрд Дювалын алгоритм $s_3$ мөрийн эхний тэмдэгтийг авч түүнийг $s_2$ мөрд залгахыг оролдоно. Хэрэв $s_2$ цаашид урьд-энгийн биш болбол $s_2$-ийн зарим хэсгийн Линдоны задаргаа мэдэгдэх болж, энэ хэсэг $s_1$ рүү шилжинэ.
Алгоритмыг илүү дэлгэрэнгүй тайлбарлая. $i$ заагч үргэлж $s_2$ мөрийн эхлэлийг заана. Гадаад давталт $i < n$ байх хүртэл гүйцэтгэгдэнэ. Давталтын дотор бид нэмэлт хоёр заагч ашиглана: $s_3$-ийн эхлэлийг заах $j$, мөн бидний одоо харьцуулж буй тэмдэгтийг заах $k$. Бид $s[j]$ тэмдэгтийг $s_2$ мөрд нэмэхийг хүсэж байгаа бөгөөд энэ нь $s[k]$ тэмдэгттэй харьцуулахыг шаардана. Гурван өөр тохиолдол байж болно:
- $s[j] = s[k]$: хэрэв ийм бол $s[j]$ тэмдэгтийг $s_2$-д нэмэх нь түүний урьд-энгийн чанарыг зөрчихгүй. Тиймээс бид $j$ ба $k$ заагчийг зүгээр л нэгээр нэмэгдүүлнэ.
- $s[j] > s[k]$: энд $s_2 + s[j]$ мөр энгийн болно. Бид $j$-г нэмэгдүүлж, $k$-г $s_2$-ийн эхлэл рүү буцаан тохируулж болох ба ингэснээр дараагийн тэмдэгтийг энгийн үгийн эхлэлтэй харьцуулж болно.
- $s[j] < s[k]$: $s_2 + s[j]$ мөр цаашид урьд-энгийн биш болно. Тиймээс бид урьд-энгийн $s_2$ мөрийг түүний энгийн мөрүүд ба үлдэгдэл (хоосон байж болно) болгон хуваана. Энгийн мөр нь $j - k$ урттай байна. Дараагийн давталтад бид үлдсэн $s_2$-оос дахин эхэлнэ.
Implementation¶
Here we present the implementation of the Duval algorithm, which will return the desired Lyndon factorization of a given string $s$.
vector<string> duval(string const& s) {
int n = s.size();
int i = 0;
vector<string> factorization;
while (i < n) {
int j = i + 1, k = i;
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j])
k = i;
else
k++;
j++;
}
while (i <= k) {
factorization.push_back(s.substr(i, j - k));
i += j - k;
}
}
return factorization;
}
Complexity¶
Энэ алгоритмын ажиллах хугацааг үнэлье.
Гадаад while давталт $n$ давталтаас хэтрэхгүй, учир нь давталт бүрийн төгсгөлд $i$ өснө. Мөн хоёр дахь дотоод while давталт $O(n)$-д ажиллана, учир нь энэ нь зөвхөн эцсийн задаргааг гаргана.
Тиймээс бид зөвхөн эхний дотоод while давталтыг сонирхож байна. Энэ нь хамгийн муу тохиолдолд хэдэн давталт гүйцэтгэх вэ? Гадаад давталтын давталт бүрд бидний тодорхойлдог энгийн үгс нь бидний нэмэлтээр харьцуулсан үлдэгдлээс урт болохыг харахад амархан. Тиймээс үлдэгдлүүдийн нийлбэр ч мөн $n$-ээс бага байх бөгөөд энэ нь бид эхний дотоод while давталтын хамгийн ихдээ $O(n)$ давталт л гүйцэтгэнэ гэсэн үг юм. Үнэндээ тэмдэгт харьцуулалтын нийт тоо $4n - 3$-аас хэтрэхгүй.
Хамгийн бага циклик шилжилтийг олох¶
$s$ тэмдэгт мөр байг. Бид $s + s$ мөрийн Линдоны задаргааг ($O(n)$ хугацаанд) байгуулна. Бид задаргаанаас $n$-ээс бага байрлалд эхэлж (өөрөөр хэлбэл $s$-ийн эхний хувилбарт эхэлж), $n$-ээс их буюу тэнцүү байрлалд ($s$-ийн хоёр дахь хувилбарт) дуусах энгийн мөрийг хайна. Энэ энгийн мөрийн эхлэлийн байрлал нь хүссэн хамгийн бага циклик шилжилтийн эхлэл байна гэж батлагдсан. Үүнийг Линдоны задаргааны тодорхойлолт ашиглан амархан шалгаж болно.
Энгийн блокийн эхлэлийг амархан олж болно — зүгээр л одоогийн урьд-энгийн мөрийн эхлэлийг заасан, гадаад давталтын давталт бүрийн эхэн дэх $i$ заагчийг сана.
Тиймээс бид дараах хэрэгжүүлэлтийг авна:
string min_cyclic_string(string s) {
s += s;
int n = s.size();
int i = 0, ans = 0;
while (i < n / 2) {
ans = i;
int j = i + 1, k = i;
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j])
k = i;
else
k++;
j++;
}
while (i <= k)
i += j - k;
}
return s.substr(ans, n / 2);
}