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

Дагаврын автомат

Дагаврын автомат гэдэг нь тэмдэгт мөртэй холбоотой олон бодлого бодох боломж олгодог хүчирхэг өгөгдлийн бүтэц юм.

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

Зөнгөөрөө бол дагаврын автоматыг өгөгдсөн тэмдэгт мөрийн бүх дэд мөрийн шахсан хэлбэр гэж ойлгож болно. Дагаврын автомат энэ бүх мэдээллийг маш өндөр шахсан хэлбэрээр агуулдаг нь гайхалтай баримт юм. $n$ урттай тэмдэгт мөрийн хувьд энэ нь ердөө $O(n)$ санах ой шаардана. Түүнчлэн үүнийг мөн $O(n)$ хугацаанд байгуулж болно (хэрэв бид цагаан толгойн хэмжээ $k$-г тогтмол гэж үзвэл), эс бөгөөс санах ой ба time complexity хоёулаа $O(n \log k)$ байх болно.

Дагаврын автоматын хэмжээний шугаман чанарыг анх 1983 онд Blumer нар нээсэн ба 1985 онд байгуулах эхний шугаман алгоритмыг Crochemore, Blumer нар танилцуулсан.

Дагаврын автоматын тодорхойлолт

Өгөгдсөн $s$ тэмдэгт мөрийн дагаврын автомат гэдэг нь $s$ тэмдэгт мөрийн бүх дагаврыг хүлээн авдаг хамгийн бага DFA (детерминистик төгсгөлөг автомат / детерминистик төгсгөлөг төлөвт машин) юм.

Өөрөөр хэлбэл:

  • Дагаврын автомат гэдэг нь чиглэлтэй циклгүй граф юм. Оройнуудыг төлөв, ирмэгүүдийг төлөв хоорондын шилжилт гэж нэрлэнэ.
  • Төлвүүдийн нэг $t_0$ нь эхлэлийн төлөв бөгөөд энэ нь графын эх байх ёстой (бусад бүх төлөвт $t_0$-ээс хүрч болно).
  • Шилжилт бүр ямар нэг тэмдэгтээр тэмдэглэгдсэн байна. Нэг төлвөөс гарах бүх шилжилт ялгаатай тэмдэглэгээтэй байх ёстой.
  • Нэг буюу хэд хэдэн төлөв төгсгөлийн төлөв гэж тэмдэглэгдсэн байна. Хэрэв бид эхлэлийн төлөв $t_0$-ээс эхлэн шилжилтүүдээр төгсгөлийн төлөв рүү явбал өнгөрсөн шилжилтүүдийн тэмдэглэгээ нь $s$ тэмдэгт мөрийн дагавруудын нэгийг үсэглэх ёстой. $s$-ийн дагавар бүрийг $t_0$-ээс төгсгөлийн төлөв хүртэлх зам ашиглан үсэглэж чаддаг байх ёстой.
  • Дагаврын автомат нь дээр тайлбарласан нөхцөлийг хангах бүх автоматуудаас хамгийн бага тооны орой агуулна.

Дэд мөрийн шинж чанар

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

Тайлбарыг хялбарчлахын тулд бид дэд мөр нь тэр замд харгалзана гэж хэлнэ ($t_0$-ээс эхэлж, тэмдэглэгээнүүд нь дэд мөрийг үсэглэнэ). Эсрэгээрээ бид дурын зам нь өөрийн тэмдэглэгээгээр үсэглэгдсэн тэмдэгт мөрд харгалзана гэж хэлнэ.

Нэг буюу хэд хэдэн зам төлөв рүү хөтөлж болно. Тиймээс бид төлөв нь эдгээр замд харгалзах тэмдэгт мөрүүдийн олонлогт харгалзана гэж хэлнэ.

Байгуулсан дагаврын автоматын жишээ

Энд бид хэд хэдэн энгийн тэмдэгт мөрийн дагаврын автоматын зарим жишээг үзүүлнэ.

Бид эхлэлийн төлвийг цэнхэрээр, төгсгөлийн төлвүүдийг ногооноор тэмдэглэнэ.

$s =~ \text{""}$ тэмдэгт мөрийн хувьд:

""-ийн дагаврын автомат

$s =~ \text{"a"}$ тэмдэгт мөрийн хувьд:

"a"-ийн дагаврын автомат

$s =~ \text{"aa"}$ тэмдэгт мөрийн хувьд:

"aa"-ийн дагаврын автомат

$s =~ \text{"ab"}$ тэмдэгт мөрийн хувьд:

"ab"-ийн дагаврын автомат

$s =~ \text{"aba"}$ тэмдэгт мөрийн хувьд:

"aba"-ийн дагаврын автомат

$s =~ \text{"abb"}$ тэмдэгт мөрийн хувьд:

"abb"-ийн дагаврын автомат

$s =~ \text{"abbb"}$ тэмдэгт мөрийн хувьд:

"abbb"-ийн дагаврын автомат

Шугаман хугацаанд байгуулах

Дагаврын автоматыг шугаман хугацаанд байгуулах алгоритмыг тайлбарлахаас өмнө бид байгуулалтыг ойлгоход маш чухал байх хэд хэдэн шинэ ойлголт, энгийн баталгааг танилцуулах хэрэгтэй.

End positions $endpos$

$s$ тэмдэгт мөрийн дурын хоосон биш дэд мөр $t$-г авч үз. Бид $endpos(t)$-ээр $t$-ийн орцууд дуусах $s$ тэмдэгт мөр дэх бүх байрлалын олонлогийг тэмдэглэнэ. Жишээ нь $\text{"abcbc"}$ тэмдэгт мөрийн хувьд бидэнд $endpos(\text{"bc"}) = \{2, 4\}$ байна.

Хоёр дэд мөр $t_1$ ба $t_2$-ийн төгсгөлийн олонлог давхцаж байвал буюу $endpos(t_1) = endpos(t_2)$ бол бид тэдгээрийг $endpos$-эквивалент гэж нэрлэнэ. Ингэснээр $s$ тэмдэгт мөрийн бүх хоосон биш дэд мөрийг $endpos$ олонлогийнх нь дагуу хэд хэдэн эквивалент анги болгон задалж болно.

Дагаврын машинд $endpos$-эквивалент дэд мөрүүд нэг төлөвт харгалздаг нь тогтоогддог. Өөрөөр хэлбэл дагаврын автомат дахь төлвийн тоо нь бүх дэд мөрүүдийн эквивалент ангиудын тоо дээр эхлэлийн төлвийг нэмсэнтэй тэнцүү. Дагаврын автоматын төлөв бүр ижил $endpos$ утгатай нэг буюу хэд хэдэн дэд мөрд харгалзана.

Бид хожим энэ таамаглалыг ашиглан байгуулах алгоритмыг тайлбарлана. Дараа нь бид дагаврын автоматын хамгийн бага байх чанараас бусад бүх шаардлагатай шинж чанар биелж байгааг харна. Хамгийн бага байх чанар нь Нэродын теоремоос гарна (энэ өгүүлэлд үүнийг батлахгүй).

Бид $endpos$ утгуудын талаар зарим чухал ажиглалт хийж болно:

Лемм 1: Хоёр хоосон биш дэд мөр $u$ ба $w$ ($length(u) \le length(w)$-тэй) нь $endpos$-эквивалент байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь $u$ тэмдэгт мөр $s$-д зөвхөн $w$-ийн дагавар хэлбэрээр гарч ирэх явдал юм.

Баталгаа нь илэрхий. Хэрэв $u$ ба $w$ ижил $endpos$ утгатай бол $u$ нь $w$-ийн дагавар бөгөөд $s$-д зөвхөн $w$-ийн дагавар хэлбэрээр гарч ирнэ. Хэрэв $u$ нь $w$-ийн дагавар бөгөөд $s$-д зөвхөн дагавар хэлбэрээр гарч ирвэл $endpos$ утгууд нь тодорхойлолтоор тэнцүү болно.

Лемм 2: Хоёр хоосон биш дэд мөр $u$ ба $w$-г ($length(u) \le length(w)$-тэй) авч үз. Тэгвэл тэдгээрийн $endpos$ олонлогууд огт огтлолцохгүй, эсвэл $endpos(w)$ нь $endpos(u)$-ийн дэд олонлог байна. Энэ нь $u$ нь $w$-ийн дагавар мөн эсэхээс хамаарна.

$$\begin{cases} endpos(w) \subseteq endpos(u) & \text{if } u \text{ is a suffix of } w \\\\ endpos(w) \cap endpos(u) = \emptyset & \text{otherwise} \end{cases}$$

Баталгаа: Хэрэв $endpos(u)$ ба $endpos(w)$ олонлогууд дор хаяж нэг нийтлэг элементтэй бол $u$ ба $w$ тэмдэгт мөрүүд хоёулаа тэр байрлалд дуусна, өөрөөр хэлбэл $u$ нь $w$-ийн дагавар юм. Гэвч тэгвэл $w$-ийн орц бүрд $u$ дэд мөр мөн гарч ирэх ба энэ нь $endpos(w)$ нь $endpos(u)$-ийн дэд олонлог гэсэн үг юм.

Лемм 3: $endpos$-эквивалент ангийг авч үз. Энэ анги дахь бүх дэд мөрийг урт нь буурах дарааллаар эрэмбэл. Тэгвэл үүссэн дараалалд дэд мөр бүр өмнөхөөсөө нэгээр богино байх ба нэгэн зэрэг өмнөхийнхөө дагавар байх болно. Өөрөөр хэлбэл нэг эквивалент ангид богино дэд мөрүүд нь үнэндээ урт дэд мөрүүдийн дагавар байх ба тэдгээр нь тодорхой $[x; y]$ интервал дахь бүх боломжит уртыг авна.

Баталгаа: Ямар нэг $endpos$-эквивалент ангийг тогтоо. Хэрэв энэ нь ердөө нэг тэмдэгт мөр агуулж байвал лемм илэрхий үнэн. Одоо ангид байгаа тэмдэгт мөрийн тоо нэгээс их гэж үзье.

Лемм 1-ийн дагуу хоёр өөр $endpos$-эквивалент тэмдэгт мөр үргэлж богино нь уртынхаа жинхэнэ дагавар байдаг байдалтай байна. Үүний үр дүнд эквивалент ангид ижил урттай хоёр тэмдэгт мөр байж болохгүй.

Эквивалент ангийн хамгийн урт тэмдэгт мөрийг $w$, хамгийн богиныг $u$ гэж тэмдэглэе. Лемм 1-ийн дагуу $u$ тэмдэгт мөр нь $w$ тэмдэгт мөрийн жинхэнэ дагавар юм. Одоо $[length(u); length(w)]$ интервал дахь урттай $w$-ийн дурын дагаврыг авч үз. Энэ дагавар мөн тэр эквивалент ангид агуулагдаж байгааг харахад амархан. Учир нь энэ дагавар $s$ тэмдэгт мөрд зөвхөн $w$-ийн дагавар хэлбэрээр гарч ирж чадна (учир нь илүү богино дагавар $u$ ч мөн $s$-д зөвхөн $w$-ийн дагавар хэлбэрээр гарч ирдэг). Үүний үр дүнд Лемм 1-ийн дагуу энэ дагавар нь $w$ тэмдэгт мөртэй $endpos$-эквивалент юм.

Автомат дахь ямар нэг төлөв $v \ne t_0$-г авч үз. Бидний мэдэхээр төлөв $v$ нь ижил $endpos$ утгатай тэмдэгт мөрүүдийн ангид харгалзана. Хэрэв бид эдгээр тэмдэгт мөрийн хамгийн уртыг $w$ гэж тэмдэглэвэл бусад бүх тэмдэгт мөр нь $w$-ийн дагавар болно.

Мөн $w$ тэмдэгт мөрийн эхний хэдэн дагавар (хэрэв бид дагавруудыг урт нь буурах дарааллаар авч үзвэл) бүгд энэ эквивалент ангид агуулагдах ба бусад бүх дагавар (дор хаяж нэг нь — хоосон дагавар) өөр зарим ангид байдгийг бид мэднэ. Бид ийм хамгийн том дагаврыг $t$ гэж тэмдэглээд түүн рүү дагаврын холбоос хийнэ.

Өөрөөр хэлбэл дагаврын холбоос $link(v)$ нь өөр $endpos$-эквивалент ангид байгаа $w$-ийн хамгийн урт дагаварт харгалзах төлөв рүү хөтөлнө.

Энд бид эхлэлийн төлөв $t_0$ нь өөрийн гэсэн эквивалент ангид (зөвхөн хоосон тэмдэгт мөр агуулах) харгалзана гэж үзэх ба тохиромжтой байдлын үүднээс $endpos(t_0) = \{-1, 0, \dots, length(s)-1\}$ гэж тохируулна.

Лемм 4: Дагаврын холбоосууд $t_0$ үндэстэй мод үүсгэнэ.

Баталгаа: Дурын төлөв $v \ne t_0$-г авч үз. Дагаврын холбоос $link(v)$ нь чанд бага урттай тэмдэгт мөрүүдэд харгалзах төлөв рүү хөтөлнө (энэ нь дагаврын холбоосын тодорхойлолт ба Лемм 3-аас гарна). Тиймээс дагаврын холбоосуудаар явснаар бид эрт орой хэзээ нэгэн цагт хоосон тэмдэгт мөрд харгалзах эхлэлийн төлөв $t_0$-д хүрнэ.

Лемм 5: Хэрэв бид $endpos$ олонлогуудыг ашиглан мод байгуулбал (эцэг зангилааны олонлог нь бүх хүүхдийн олонлогийг дэд олонлог болгон агуулна гэсэн дүрмээр) бүтэц нь дагаврын холбоосын модтой давхцана.

Баталгаа: Бид $endpos$ олонлогуудыг ашиглан мод байгуулж чадна гэдэг баримт нь Лемм 2-оос шууд гарна (дурын хоёр олонлог огтлолцохгүй, эсвэл нэг нь нөгөөдөө агуулагдана).

Одоо дурын төлөв $v \ne t_0$ ба түүний дагаврын холбоос $link(v)$-г авч үзье. Дагаврын холбоосын тодорхойлолт ба Лемм 2-оос дараах нь гарна

$$endpos(v) \subseteq endpos(link(v)),$$

энэ нь өмнөх леммтэй хамт мэдэгдлийг батална: дагаврын холбоосын мод нь үндсэндээ $endpos$ олонлогуудын мод юм.

$\text{"abcbc"}$ тэмдэгт мөрийн хувьд байгуулсан дагаврын автомат дахь дагаврын холбоосын модны жишээ энд байна. Зангилаануудыг харгалзах эквивалент ангийн хамгийн урт дэд мөрөөр тэмдэглэсэн.

Дагаврын холбоос бүхий "abcbc"-ийн дагаврын автомат

Дүгнэлт

Алгоритм руу орохоос өмнө бид хуримтлуулсан мэдлэгээ дүгнэж, хэдэн туслах тэмдэглэгээ танилцуулна.

  • $s$ тэмдэгт мөрийн дэд мөрүүдийг төгсгөлийн байрлал $endpos$-ынх нь дагуу эквивалент ангиудад задалж болно.
  • Дагаврын автомат нь эхлэлийн төлөв $t_0$, мөн $endpos$-эквивалент анги бүрд нэг төлвөөс бүрдэнэ.
  • Төлөв $v$ бүрд нэг буюу хэд хэдэн дэд мөр таарна. Бид ийм хамгийн урт тэмдэгт мөрийг $longest(v)$, түүний уртыг $len(v)$ гэж тэмдэглэнэ. Бид ийм хамгийн богино дэд мөрийг $shortest(v)$, түүний уртыг $minlen(v)$ гэж тэмдэглэнэ. Тэгвэл энэ төлөвт харгалзах бүх тэмдэгт мөр нь $longest(v)$ тэмдэгт мөрийн өөр өөр дагавар байх ба $[minlen(v); len(v)]$ интервал дахь бүх боломжит урттай байна.
  • Төлөв $v \ne t_0$ бүрийн хувьд дагаврын холбоос нь $longest(v)$ тэмдэгт мөрийн $minlen(v) - 1$ урттай дагаварт харгалзах төлөв рүү хөтөлдөг холбоос гэж тодорхойлогдоно. Дагаврын холбоосууд $t_0$-д үндэстэй мод үүсгэх ба үүний зэрэгцээ энэ мод нь $endpos$ олонлогуудын хоорондох агуулагдах хамаарлыг үүсгэнэ.
  • Бид $v \ne t_0$-ийн хувьд $minlen(v)$-г дагаврын холбоос $link(v)$ ашиглан дараах байдлаар илэрхийлж болно:
$$minlen(v) = len(link(v)) + 1$$
  • Хэрэв бид дурын төлөв $v_0$-ээс эхлэн дагаврын холбоосуудыг дагавал эрт орой хэзээ нэгэн цагт бид эхлэлийн төлөв $t_0$-д хүрнэ. Энэ тохиолдолд бид $[minlen(v_i); len(v_i)]$ огтлолцолгүй интервалуудын дарааллыг авах ба тэдгээрийн нэгдэл нь $[0; len(v_0)]$ тасралтгүй интервалыг үүсгэнэ.

Алгоритм

Одоо бид алгоритм руугаа орж болно. Алгоритм нь онлайн байх болно, өөрөөр хэлбэл бид тэмдэгт мөрийн тэмдэгтүүдийг нэг нэгээр нь нэмж, алхам бүрд автоматыг зохих ёсоор өөрчилнө.

Шугаман санах ойн хэрэглээнд хүрэхийн тулд бид төлөв бүрд зөвхөн $len$, $link$ утга ба шилжилтүүдийн жагсаалтыг хадгална. Бид төгсгөлийн төлвүүдийг тэмдэглэхгүй (гэхдээ дагаврын автоматыг байгуулсны дараа эдгээр тэмдэглэгээг хэрхэн байрлуулахыг хожим үзүүлнэ).

Эхэндээ автомат нь ганц төлөв $t_0$-ээс бүрдэх ба энэ нь $0$ индекстэй байна (үлдсэн төлвүүд $1, 2, \dots$ индексүүдийг авна). Бид тохиромжтой байдлын үүднээс түүнд $len = 0$ ба $link = -1$ гэж ононо ($-1$ нь зохиомол, оршин байдаггүй төлөв байх болно).

Одоо бүх бодлого нь одоогийн тэмдэгт мөрийн төгсгөлд нэг тэмдэгт $c$ нэмэх үйл явцыг хэрэгжүүлэх болтол буурч байна. Энэ үйл явцыг тайлбарлая:

  • $last$ нь $c$ тэмдэгтийг нэмэхийн өмнөх бүтэн тэмдэгт мөрд харгалзах төлөв байг. (Эхэндээ бид $last = 0$ гэж тохируулах ба алгоритмын сүүлийн алхамд $last$-ыг зохих ёсоор өөрчилнө.)
  • Шинэ төлөв $cur$ үүсгээд түүнд $len(cur) = len(last) + 1$ гэж оноо. $link(cur)$ утга энэ үед мэдэгдэхгүй байна.
  • Одоо бид дараах үйлдлийг гүйцэтгэнэ: Бид $last$ төлвөөс эхэлнэ. $c$ үсгээр шилжилт байхгүй л бол бид $cur$ төлөв рүү шилжилт нэмээд дагаврын холбоосыг дагана. Хэрэв ямар нэг үед $c$ үсгээр шилжилт аль хэдийн байвал бид зогсоод энэ төлвийг $p$ гэж тэмдэглэнэ.
  • Хэрэв бид ийм төлөв $p$-г олоогүй бол зохиомол төлөв $-1$-д хүрсэн гэсэн үг тул бид зүгээр л $link(cur) = 0$ гэж оноогоод гарч болно.
  • Одоо бид $c$ үсгээр шилжилт байгаа $p$ төлвийг оллоо гэж үзье. Шилжилт хөтөлж буй төлвийг бид $q$ гэж тэмдэглэнэ.
  • Одоо бидэнд хоёр тохиолдол байна. $len(p) + 1 = len(q)$ байх, эсвэл байхгүй.
  • Хэрэв $len(p) + 1 = len(q)$ бол бид зүгээр л $link(cur) = q$ гэж оноогоод гарч болно.

  • Эс бөгөөс арай илүү төвөгтэй. $q$ төлвийг хувилах шаардлагатай: бид шинэ төлөв $clone$ үүсгээд $len$ утгаас бусад бүх өгөгдлийг (дагаврын холбоос ба шилжилтүүд) $q$-ээс хуулна. Бид $len(clone) = len(p) + 1$ гэж ононо.

    Хувилсны дараа бид $cur$-ээс $clone$ руу, мөн $q$-ээс $clone$ руу дагаврын холбоосыг чиглүүлнэ.

    Эцэст нь бид $p$ төлвөөс дагаврын холбоосуудыг ашиглан ухарч явах хэрэгтэй бөгөөд $c$-ээр $q$ төлөв рүү шилжилт байсаар байх хугацаанд тэдгээрийг бүгдийг $clone$ төлөв рүү дахин чиглүүлнэ.

  • Гурван тохиолдлын алинд ч гэсэн үйлдлийг дуусгасны дараа бид $last$ утгыг $cur$ төлвөөр шинэчилнэ.

Хэрэв бид аль төлвүүд нь төгсгөлийн төлөв, аль нь биш болохыг мөн мэдэхийг хүсвэл бүтэн $s$ тэмдэгт мөрийн бүрэн дагаврын автоматыг байгуулсны дараа бүх төгсгөлийн төлвийг олж болно. Үүний тулд бид бүтэн тэмдэгт мөрд харгалзах төлвийг ($last$ хувьсагчид хадгалагдсан) авч, эхлэлийн төлөвт хүртэл түүний дагаврын холбоосуудыг дагана. Бид зочилсон бүх төлвийг төгсгөлийн төлөв гэж тэмдэглэнэ. Ингэснээр бид $s$ тэмдэгт мөрийн бүх дагаварт харгалзах төлвүүдийг яг таг тэмдэглэх бөгөөд эдгээр нь яг төгсгөлийн төлвүүд болохыг ойлгоход амархан.

Дараагийн хэсэгт бид алхам бүрийг нарийвчлан авч үзэж, түүний зөв байдлыг харуулна.

Энд бид зөвхөн $s$-ийн тэмдэгт бүрд ганц эсвэл хоёр шинэ төлөв үүсгэдэг тул дагаврын автомат нь шугаман тооны төлөв агуулна гэдгийг тэмдэглэе.

Шилжилтийн тооны шугаман чанар, ерөнхийдөө алгоритмын ажиллах хугацааны шугаман чанар нь тийм ч тодорхой биш бөгөөд бид зөв байдлыг баталсны дараа тэдгээрийг батлах болно.

Зөв байдал

  • Хэрэв $len(p) + 1 = len(q)$ бол бид $(p, q)$ шилжилтийг тасралтгүй гэж нэрлэнэ. Эс бөгөөс буюу $len(p) + 1 < len(q)$ үед шилжилтийг тасралтгүй бус гэж нэрлэнэ.

    Алгоритмын тайлбараас харахад тасралтгүй ба тасралтгүй бус шилжилтүүд алгоритмын өөр өөр тохиолдол руу хөтөлнө. Тасралтгүй шилжилтүүд тогтмол бөгөөд хэзээ ч дахин өөрчлөгдөхгүй. Үүний эсрэгээр тэмдэгт мөрд шинэ үсэг нэмэгдэх үед тасралтгүй бус шилжилт өөрчлөгдөж болно (шилжилтийн ирмэгийн төгсгөл өөрчлөгдөж болно).

  • Хоёрдмол утга гаргахгүйн тулд бид одоогийн $c$ тэмдэгтийг нэмэхээс өмнө дагаврын автоматыг нь байгуулсан тэмдэгт мөрийг $s$ гэж тэмдэглэнэ.

  • Алгоритм нь бүтэн $s + c$ тэмдэгт мөрд харгалзах шинэ төлөв $cur$ үүсгэхээс эхэлнэ. Бид яагаад шинэ төлөв үүсгэх ёстой нь тодорхой. Шинэ тэмдэгттэй хамт шинэ эквивалент анги үүснэ.

  • Шинэ төлөв үүсгэсний дараа бид бүтэн $s$ тэмдэгт мөрд харгалзах төлвөөс эхлэн дагаврын холбоосуудаар явна. Төлөв бүрийн хувьд бид $c$ тэмдэгтээр шинэ $cur$ төлөв рүү шилжилт нэмэхийг оролдоно. Ингэснээр бид $s$-ийн дагавар бүрд $c$ тэмдэгтийг залгана. Гэвч бид эдгээр шинэ шилжилтийг зөвхөн аль хэдийн байгаа шилжилттэй зөрчилдөхгүй үед нэмж чадна. Тиймээс бид $c$-тэй аль хэдийн байгаа шилжилтийг олмогцоо зогсох ёстой.

  • Хамгийн энгийн тохиолдолд бид зохиомол төлөв $-1$-д хүрнэ. Энэ нь бид $s$-ийн бүх дагаварт $c$-тэй шилжилт нэмсэн гэсэн үг юм. Мөн энэ нь $c$ тэмдэгт өмнө нь $s$ тэмдэгт мөрийн хэсэг байгаагүй гэсэн үг юм. Тиймээс $cur$-ийн дагаврын холбоос $0$ төлөв рүү хөтлөх ёстой.

  • Хоёр дахь тохиолдолд бид аль хэдийн байгаа $(p, q)$ шилжилттэй тулгарна. Энэ нь бид машинд аль хэдийн байгаа $x + c$ тэмдэгт мөрийг ($x$ нь $s$-ийн дагавар) машинд нэмэхийг оролдсон гэсэн үг юм ($x + c$ тэмдэгт мөр $s$-ийн дэд мөр хэлбэрээр аль хэдийн гарч ирсэн байна). Бид $s$ тэмдэгт мөрийн автоматыг зөв байгуулсан гэж үзэж байгаа тул энд шинэ шилжилт нэмэх ёсгүй.

    Гэвч нэг бэрхшээл байна. $cur$ төлвөөс гарах дагаврын холбоос аль төлөв рүү хөтлөх ёстой вэ? Бид хамгийн урт тэмдэгт мөр нь яг $x + c$ байх төлөв рүү дагаврын холбоос хийх ёстой, өөрөөр хэлбэл энэ төлвийн $len$ нь $len(p) + 1$ байх ёстой. Гэвч ийм төлөв хараахан байхгүй байх боломжтой, өөрөөр хэлбэл $len(q) > len(p) + 1$. Энэ тохиолдолд бид $q$ төлвийг хувааж ийм төлөв үүсгэх хэрэгтэй.

  • Хэрэв $(p, q)$ шилжилт тасралтгүй байвал $len(q) = len(p) + 1$ болно. Энэ тохиолдолд бүх зүйл энгийн. Бид $cur$-ээс $q$ төлөв рүү дагаврын холбоосыг чиглүүлнэ.

  • Эс бөгөөс шилжилт тасралтгүй бус, өөрөөр хэлбэл $len(q) > len(p) + 1$ байна. Энэ нь $q$ төлөв нь зөвхөн $len(p) + 1$ урттай $s + c$-ийн дагаварт төдийгүй $s$-ийн илүү урт дэд мөрүүдэд ч харгалзана гэсэн үг юм. Бид $q$ төлвийг эхнийх нь $len(p) + 1$ урттай байхаар хоёр дэд төлөв болгон хуваахаас өөр юу ч хийж чадахгүй.

    Бид төлвийг хэрхэн хувааж чадах вэ? Бид $q$ төлвийг хувилах ба энэ нь бидэнд $clone$ төлвийг өгөх бөгөөд бид $len(clone) = len(p) + 1$ гэж тохируулна. Бид $q$-ээр дамжин өнгөрөх замуудыг өөрчлөхийг хүсэхгүй байгаа тул бүх шилжилтийг $q$-ээс $clone$ руу хуулна. Мөн бид $clone$-оос $q$-ийн дагаврын холбоосын очих газар руу дагаврын холбоос тавьж, $q$-ийн дагаврын холбоосыг $clone$ болгож тохируулна.

    Төлвийг хуваасны дараа бид $cur$-ээс $clone$ руу дагаврын холбоос тавина.

    Сүүлийн алхамд бид $q$ руу чиглэсэн зарим шилжилтийг өөрчилж, тэдгээрийг $clone$ руу дахин чиглүүлнэ. Бид аль шилжилтийг өөрчлөх ёстой вэ? Зөвхөн $w + c$ тэмдэгт мөрийн бүх дагаварт харгалзах шилжилтүүдийг дахин чиглүүлэхэд хангалттай ($w$ нь $p$-ийн хамгийн урт тэмдэгт мөр), өөрөөр хэлбэл бид $p$ оройноос эхлэн зохиомол төлөв $-1$-д хүрэх юм уу $q$-ээс өөр төлөв рүү хөтлөх шилжилттэй тулгартал дагаврын холбоосуудын дагуу үргэлжлүүлэн явах хэрэгтэй.

Шугаман тооны үйлдэл

Эхлээд бид цагаан толгойн хэмжээ тогтмол гэсэн таамаглалыг шууд гаргана. Хэрэв тийм биш бол шугаман time complexity-ийн талаар ярих боломжгүй болно. Нэг оройноос гарах шилжилтүүдийн жагсаалтыг тэнцвэржүүлсэн модонд хадгалах ба энэ нь түлхүүр хайх, түлхүүр нэмэх үйлдлийг хурдан гүйцэтгэх боломж олгоно. Тиймээс бид цагаан толгойн хэмжээг $k$ гэж тэмдэглэвэл алгоритмын асимптот зан төлөв нь $O(n)$ санах ойтойгоор $O(n \log k)$ байх болно. Гэвч цагаан толгой хангалттай жижиг бол та тэнцвэржүүлсэн мод ашиглахаас зайлсхийж, санах ойгоор золиослон орой бүрийн шилжилтүүдийг $k$ урттай массив (түлхүүрээр хурдан хайхын тулд) ба динамик жагсаалт (боломжтой бүх түлхүүрийг хурдан тойрохын тулд) хэлбэрээр хадгалж болно. Ингэснээр бид алгоритмын хувьд $O(n)$ time complexity-д хүрэх боловч $O(n k)$ санах ойн complexity-ийн зардлаар.

Тиймээс бид цагаан толгойн хэмжээг тогтмол гэж үзнэ, өөрөөр хэлбэл тэмдэгтээр шилжилт хайх, шилжилт нэмэх, дараагийн шилжилтийг хайх үйлдэл бүр — эдгээр бүх үйлдлийг $O(1)$-д хийж болно.

Хэрэв бид алгоритмын бүх хэсгийг авч үзвэл шугаман complexity нь илэрхий биш гурван байрлал байна:

  • Эхний байрлал нь $last$ төлвөөс дагаврын холбоосуудаар тойрч $c$ тэмдэгттэй шилжилт нэмэх явдал юм.
  • Хоёр дахь байрлал нь $q$ төлвийг шинэ $clone$ төлөв болгон хувилах үед шилжилтүүдийг хуулах явдал юм.
  • Гурав дахь байрлал нь $q$ руу хөтлөх шилжилтүүдийг өөрчилж, тэдгээрийг $clone$ руу дахин чиглүүлэх явдал юм.

Бид дагаврын автоматын хэмжээ (төлвийн тоо ба шилжилтийн тооны аль алинаар нь) шугаман байдаг гэсэн баримтыг ашиглана. (Төлвийн тооны шугаман чанарын баталгаа нь алгоритм өөрөө бөгөөд төлвийн тооны шугаман чанарын баталгааг доор, алгоритмын хэрэгжүүлэлтийн дараа өгсөн болно).

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

Анх $q$ руу заасан шилжилтүүдийг $clone$ руу дахин чиглүүлдэг гурав дахь байрлалын нийт complexity-г үнэлэх нь үлдэж байна. Бид $v = longest(p)$ гэж тэмдэглэнэ. Энэ нь $s$ тэмдэгт мөрийн дагавар бөгөөд итерац бүрд түүний урт багасна — тиймээс $s$ тэмдэгт мөрийн дагавар болох $v$-ийн байрлал итерац бүрд монотоноор өснө. Энэ тохиолдолд хэрэв давталтын эхний итерацаас өмнө харгалзах $v$ тэмдэгт мөр $last$-аас $k$ ($k \ge 2$) гүнд байсан бол (гүнийг дагаврын холбоосын тоогоор тоолж), сүүлийн итерацын дараа $v + c$ тэмдэгт мөр нь $cur$-ээс (шинэ $last$ утга болох) эхлэх зам дээрх $2$ дахь дагаврын холбоос байх болно.

Ингэснээр энэ давталтын итерац бүр нь одоогийн тэмдэгт мөрийн дагавар болох $longest(link(link(last))$ тэмдэгт мөрийн байрлал монотоноор өсөхөд хүргэнэ. Тиймээс энэ цикл $n$-ээс олон итерац гүйцэтгэж чадахгүй бөгөөд үүнийг батлах шаардлагатай байсан.

Implementation

First we describe a data structure that will store all information about a specific transition ($len$, $link$ and the list of transitions). If necessary you can add a terminal flag here, as well as other information. We will store the list of transitions in the form of a $map$, which allows us to achieve total $O(n)$ memory and $O(n \log k)$ time for processing the entire string.

struct state {
    int len, link;
    map<char, int> next;
};

The suffix automaton itself will be stored in an array of these structures $state$. We store the current size $sz$ and also the variable $last$, the state corresponding to the entire string at the moment.

const int MAXLEN = 100000;
state st[MAXLEN * 2];
int sz, last;

We give a function that initializes a suffix automaton (creating a suffix automaton with a single state).

void sa_init() {
    st[0].len = 0;
    st[0].link = -1;
    sz++;
    last = 0;
}

And finally we give the implementation of the main function - which adds the next character to the end of the current line, rebuilding the machine accordingly.

void sa_extend(char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p = last;
    while (p != -1 && !st[p].next.count(c)) {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if (p == -1) {
        st[cur].link = 0;
    } else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) {
            st[cur].link = q;
        } else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            while (p != -1 && st[p].next[c] == q) {
                st[p].next[c] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

As mentioned above, if you sacrifice memory ($O(n k)$, where $k$ is the size of the alphabet), then you can achieve the build time of the machine in $O(n)$, even for any alphabet size $k$. But for this you will have to store an array of size $k$ in each state (for quickly jumping to the transition of the letter), and additional a list of all transitions (to quickly iterate over the transitions them).

Нэмэлт шинж чанарууд

Төлвийн тоо

$n$ урттай $s$ тэмдэгт мөрийн дагаврын автомат дахь төлвийн тоо $2n - 1$-ээс хэтрэхгүй ($n \ge 2$-ын хувьд).

Баталгаа нь байгуулах алгоритм өөрөө юм, учир нь эхэндээ автомат нэг төлвөөс бүрдэх ба эхний болон хоёр дахь итерацад ердөө ганц төлөв үүсэх бөгөөд үлдсэн $n-2$ алхам бүрд хамгийн ихдээ $2$ төлөв үүснэ.

Гэвч бид энэ үнэлгээг алгоритмыг мэдэлгүйгээр ч харуулж чадна. Төлвийн тоо нь ялгаатай $endpos$ олонлогийн тоотой тэнцүү гэдгийг сануулъя. Түүнчлэн эдгээр $endpos$ олонлогууд мод үүсгэдэг (эцэг орой нь бүх хүүхдийн олонлогийг өөрийн олонлогтоо агуулна). Энэ модыг авч үзээд бага зэрэг хувиргая: ганцхан хүүхэдтэй дотоод орой байсаар байх хугацаанд (энэ нь хүүхдийн олонлог эцгийн олонлогоос дор хаяж нэг байрлалыг алдсан гэсэн үг) бид дутуу байрлалуудын олонлогтой шинэ хүүхэд үүсгэнэ. Эцэст нь бид дотоод орой бүр нь нэгээс их зэрэгтэй, навчны тоо нь $n$-ээс хэтрэхгүй модтой болно. Тиймээс ийм модонд $2n - 1$-ээс олон орой байхгүй.

Төлвийн тооны энэ хязгаарт үнэндээ $n$ бүрийн хувьд хүрч болно. Боломжит тэмдэгт мөр нь:

$$\text{"abbb}\dots \text{bbb"}$$

Гурав дахиас эхлэн итерац бүрд алгоритм нэг төлвийг хуваах ба үр дүнд яг $2n - 1$ төлөв гарна.

Шилжилтийн тоо

$n$ урттай $s$ тэмдэгт мөрийн дагаврын автомат дахь шилжилтийн тоо $3n - 4$-өөс хэтрэхгүй ($n \ge 3$-ын хувьд).

Үүнийг баталъя:

Эхлээд тасралтгүй шилжилтийн тоог үнэлье. $t_0$ төлвөөс эхлэх автомат дахь хамгийн урт замуудын тэлэх модыг авч үз. Энэ тэлэх мод зөвхөн тасралтгүй ирмэгүүдээс бүрдэх тул тэдгээрийн тоо төлвийн тооноос бага, өөрөөр хэлбэл $2n - 2$-оос хэтрэхгүй.

Одоо тасралтгүй бус шилжилтийн тоог үнэлье. Одоогийн тасралтгүй бус шилжилт нь $c$ тэмдэгттэй $(p, q)$ байг. Бид харгалзах $u + c + w$ тэмдэгт мөрийг авна, энд $u$ тэмдэгт мөр нь эхлэлийн төлвөөс $p$ хүртэлх хамгийн урт замд, $w$ нь $q$-ээс дурын төгсгөлийн төлөв хүртэлх хамгийн урт замд харгалзана. Нэг талаас, бүрэн бус тэмдэгт мөр бүрийн хувьд ийм $u + c + w$ тэмдэгт мөр бүр ялгаатай байна ($u$ ба $w$ тэмдэгт мөрүүд зөвхөн бүрэн шилжилтүүдээр үүсдэг тул). Нөгөө талаас, ийм $u + c + w$ тэмдэгт мөр бүр төгсгөлийн төлвийн тодорхойлолтоор бүтэн $s$ тэмдэгт мөрийн дагавар байна. $s$-ийн хоосон биш дагавар ердөө $n$ ширхэг байдаг бөгөөд $u + c + w$ тэмдэгт мөрүүдийн аль нь ч $s$-ийг агуулж чадахгүй тул (учир нь бүтэн тэмдэгт мөр зөвхөн бүрэн шилжилтүүд агуулна) бүрэн бус шилжилтийн нийт тоо $n - 1$-ээс хэтрэхгүй.

Эдгээр хоёр үнэлгээг нэгтгэвэл бидэнд $3n - 3$ хязгаар гарна. Гэвч төлвийн хамгийн их тоонд зөвхөн $\text{"abbb\dots bbb"}$ тест тохиолдлоор хүрч болох ба энэ тохиолдол илэрхий $3n - 3$-аас цөөн шилжилттэй тул бид дагаврын автомат дахь шилжилтийн тооны хувьд илүү чанд $3n - 4$ хязгаарыг олж авна.

Энэ хязгаарт мөн дараах тэмдэгт мөрөөр хүрч болно:

$$\text{"abbb}\dots \text{bbbc"}$$

Хэрэглээ

Энд бид дагаврын автомат ашиглан бодож болох зарим бодлогыг авч үзнэ. Хялбар байдлын үүднээс бид цагаан толгойн хэмжээ $k$-г тогтмол гэж үзэх ба энэ нь тэмдэгт залгах ба тойролтын complexity-г тогтмол гэж үзэх боломж олгоно.

Орц шалгах

$T$ текст ба олон $P$ хэв маяг өгөгдсөн. Бид $P$ тэмдэгт мөрүүд $T$-ийн дэд мөр хэлбэрээр гарч ирж байгаа эсэхийг шалгах ёстой.

Бид $T$ текстийн дагаврын автоматыг $O(length(T))$ хугацаанд байгуулна. $P$ хэв маяг $T$-д гарч ирж байгаа эсэхийг шалгахын тулд бид $t_0$-ээс эхлэн $P$-ийн тэмдэгтүүдийн дагуу шилжилтүүдийг дагана. Хэрэв ямар нэг үед шилжилт байхгүй бол $P$ хэв маяг $T$-ийн дэд мөр хэлбэрээр гарч ирэхгүй. Хэрэв бид бүтэн $P$ тэмдэгт мөрийг ийм байдлаар боловсруулж чадвал тэмдэгт мөр $T$-д гарч ирнэ.

Энэ нь $P$ тэмдэгт мөр бүрийн хувьд $O(length(P))$ хугацаа авах нь тодорхой. Түүнчлэн алгоритм үнэндээ текстэд гарч ирэх $P$-ийн хамгийн урт угтварын уртыг олно.

Ялгаатай дэд мөрийн тоо

$S$ тэмдэгт мөр өгөгдсөн. Та ялгаатай дэд мөрийн тоог тооцоолохыг хүсэж байна.

$S$ тэмдэгт мөрийн дагаврын автоматыг байгуулъя.

$S$-ийн дэд мөр бүр автомат дахь ямар нэг замд харгалзана. Тиймээс ялгаатай дэд мөрийн тоо нь $t_0$-ээс эхлэх автомат дахь ялгаатай замын тоотой тэнцүү.

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

Тодруулбал $d[v]$ нь $v$ төлвөөс эхлэх замын тоо байг (тэг урттай замыг оруулаад). Тэгвэл бидэнд дараах рекуррент хамаарал байна:

$$d[v] = 1 + \sum_{w : (v, w, c) \in DAWG} d[w]$$

Өөрөөр хэлбэл $d[v]$-г $v$-ийн шилжилтүүдийн бүх төгсгөлийн хариултуудын нийлбэрээр илэрхийлж болно.

Ялгаатай дэд мөрийн тоо нь $d[t_0] - 1$ утга юм (учир нь бид хоосон дэд мөрийг тоолохгүй).

Нийт time complexity: $O(length(S))$

Өөр аргаар бид төлөв $v$ бүр $[minlen(v),len(v)]$ урттай дэд мөрүүдэд таардаг гэсэн баримтыг ашиглаж болно. Тиймээс $minlen(v) = 1 + len(link(v))$ гэдгийг харгалзвал $v$ төлөв дэх ялгаатай дэд мөрийн нийт тоо $len(v) - minlen(v) + 1 = len(v) - (1 + len(link(v))) + 1 = len(v) - len(link(v))$ болно.

Үүнийг доор товчхон үзүүлэв:

long long get_diff_strings(){
    long long tot = 0;
    for(int i = 1; i < sz; i++) {
        tot += st[i].len - st[st[i].link].len;
    }
    return tot;
}

Энэ нь мөн $O(length(S))$ боловч нэмэлт санах ой болон рекурсив дуудлага шаардахгүй тул үр дүнд нь практикт илүү хурдан ажиллана.

Бүх ялгаатай дэд мөрийн нийт урт

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

Шийдэл нь өмнөхтэй төстэй, зөвхөн одоо динамик программчлалын хэсэгт хоёр хэмжигдэхүүнийг авч үзэх шаардлагатай: ялгаатай дэд мөрийн тоо $d[v]$ ба тэдгээрийн нийт урт $ans[v]$.

Бид өмнөх бодлогод $d[v]$-г хэрхэн тооцоолохыг аль хэдийн тайлбарласан. $ans[v]$ утгыг дараах рекуррент хамаарал ашиглан тооцоолж болно:

$$ans[v] = \sum_{w : (v, w, c) \in DAWG} d[w] + ans[w]$$

Бид зэргэлдээ орой $w$ бүрийн хариултыг аваад түүн дээр $d[w]$-г нэмнэ (учир нь $v$ төлвөөс эхлэхэд дэд мөр бүр нэг тэмдэгтээр урт болно).

Энэ бодлогыг мөн $O(length(S))$ хугацаанд тооцоолж болно.

Өөр аргаар бид дахин төлөв $v$ бүр $[minlen(v),len(v)]$ урттай дэд мөрүүдэд таардаг гэсэн баримтыг ашиглаж болно. $minlen(v) = 1 + len(link(v))$ бөгөөд арифметик прогрессийн $S_n = n \cdot \frac{a_1+a_n}{2}$ томьёо байдаг тул ($S_n$ нь $n$ гишүүний нийлбэрийг, $a_1$ нь эхний гишүүнийг, $a_n$ нь сүүлчийн гишүүнийг илэрхийлнэ) бид нэг төлөв дэх дэд мөрүүдийн уртыг тогтмол хугацаанд тооцоолж чадна. Дараа нь бид эдгээр нийлбэрийг автомат дахь $v \neq t_0$ төлөв бүрийн хувьд нэмнэ. Үүнийг доорх кодоор үзүүлэв:

long long get_tot_len_diff_substings() {
    long long tot = 0;
    for(int i = 1; i < sz; i++) {
        long long shortest = st[st[i].link].len + 1;
        long long longest = st[i].len;

        long long num_strings = longest - shortest + 1;
        long long cur = num_strings * (longest + shortest) / 2;
        tot += cur;
    }
    return tot;
}

Энэ арга $O(length(S))$ хугацаанд ажиллах боловч туршилтаар санамсаргүй тэмдэгт мөрүүд дээр мемоизаци хийсэн динамик программчлалын хувилбараас 20 дахин хурдан ажилладаг. Энэ нь нэмэлт санах ой болон рекурс шаардахгүй.

Лексикографын $k$-р дэд мөр

$S$ тэмдэгт мөр өгөгдсөн. Бид олон асуулгад хариулах ёстой. Өгөгдсөн $K_i$ тоо бүрийн хувьд бид бүх дэд мөрийн лексикографын дарааллаар эрэмбэлсэн жагсаалт дахь $K_i$-р тэмдэгт мөрийг олох ёстой.

Энэ бодлогын шийдэл нь өмнөх хоёр бодлогын санаан дээр тулгуурлана. Лексикографын $k$-р дэд мөр нь дагаврын автомат дахь лексикографын $k$-р замд харгалзана. Тиймээс төлөв бүрээс гарах замын тоог тоолсны дараа бид автоматын үндэснээс эхлэн $k$-р замыг хялбархан хайж чадна.

Энэ нь урьдчилсан боловсруулалтад $O(length(S))$ хугацаа, дараа нь асуулга бүрд $O(length(ans) \cdot k)$ хугацаа авна ($ans$ нь асуулгын хариулт, $k$ нь цагаан толгойн хэмжээ).

Хамгийн бага циклик шилжилт

$S$ тэмдэгт мөр өгөгдсөн. Бид лексикографийн хамгийн бага циклик шилжилтийг олохыг хүсэж байна.

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

Үүний үр дүнд бодлого нь $length(S)$ урттай лексикографийн хамгийн бага замыг олох болтол хураагдах ба үүнийг энгийн аргаар хийж болно: бид эхлэлийн төлвөөс эхлээд greedy байдлаар хамгийн бага тэмдэгттэй шилжилтүүдээр дамжина.

Нийт time complexity нь $O(length(S))$.

Орцын тоо

$T$ текст өгөгдсөн. Бид олон асуулгад хариулах ёстой. Өгөгдсөн $P$ хэв маяг бүрийн хувьд бид $P$ тэмдэгт мөр $T$ тэмдэгт мөрд дэд мөр хэлбэрээр хэдэн удаа гарч ирэхийг олох ёстой.

Бид $T$ текстийн дагаврын автоматыг байгуулна.

Дараа нь бид дараах урьдчилсан боловсруулалтыг хийнэ: автомат дахь төлөв $v$ бүрийн хувьд бид $endpos(v)$ олонлогийн хэмжээтэй тэнцүү $cnt[v]$ тоог тооцоолно. Үнэндээ нэг $v$ төлөвт харгалзах бүх тэмдэгт мөр $T$ текстэд ижил тоогоор гарч ирэх ба энэ нь $endpos$ олонлог дахь байрлалын тоотой тэнцүү байна.

Гэвч бид $endpos$ олонлогуудыг шууд байгуулж чадахгүй тул зөвхөн тэдгээрийн $cnt$ хэмжээг авч үзнэ.

Тэдгээрийг тооцоолохын тулд бид дараах байдлаар үргэлжлүүлнэ. Төлөв бүрийн хувьд хэрэв тэр нь хувилах замаар үүсээгүй бол (мөн эхлэлийн төлөв $t_0$ биш бол) бид түүнийг $cnt = 1$ гэж эхлүүлнэ. Дараа нь бид бүх төлвийг $len$ уртынх нь буурах дарааллаар явж, одоогийн $cnt[v]$ утгыг дагаврын холбоосууд дээр нэмнэ:

$$cnt[link(v)] \text{ += } cnt[v]$$

Энэ нь төлөв бүрийн хувьд зөв утгыг өгнө.

Яагаад энэ зөв вэ? Хувилах замаар биш аргаар олдсон төлвийн нийт тоо яг $length(T)$ бөгөөд тэдгээрийн эхний $i$ нь бид эхний $i$ тэмдэгтийг нэмэх үед гарч ирсэн. Үүний үр дүнд эдгээр төлөв бүрийн хувьд бид түүнийг боловсруулсан харгалзах байрлалыг тоолно. Тиймээс эхэндээ бид ийм төлөв бүрд $cnt = 1$, бусад бүгдэд $cnt = 0$ гэж авна.

Дараа нь бид $v$ бүрийн хувьд дараах үйлдлийг хэрэглэнэ: $cnt[link(v)] \text{ += } cnt[v]$. Үүний ард байгаа утга нь хэрэв $v$ тэмдэгт мөр $cnt[v]$ удаа гарч ирвэл түүний бүх дагавар мөн яг тэр төгсгөлийн байрлалуудад, тиймээс мөн $cnt[v]$ удаа гарч ирнэ гэсэн үг юм.

Яагаад бид энэ үйл явцад давхар тоолохгүй вэ (өөрөөр хэлбэл зарим байрлалыг хоёр удаа тоолохгүй вэ)? Учир нь бид нэг төлвийн байрлалуудыг зөвхөн нэг өөр төлөв дээр нэмдэг тул нэг төлөв өөрийн байрлалуудыг өөр төлөв рүү хоёр өөр замаар хоёр удаа чиглүүлэх нь тохиолдож болохгүй.

Ингэснээр бид автомат дахь бүх төлвийн $cnt$ хэмжигдэхүүнийг $O(length(T))$ хугацаанд тооцоолж чадна.

Үүний дараа асуулгад хариулахдаа зүгээр л $cnt[t]$ утгыг хайна, энд $t$ нь хэв маягт харгалзах төлөв бөгөөд ийм төлөв байгаа тохиолдолд. Эс бөгөөс $0$ гэж хариул. Асуулгад хариулахад $O(length(P))$ хугацаа зарцуулна.

Эхний орцын байрлал

$T$ текст ба олон асуулга өгөгдсөн. Асуулгын $P$ тэмдэгт мөр бүрийн хувьд бид $T$ тэмдэгт мөр дэх $P$-ийн эхний орцын байрлалыг ($P$-ийн эхлэлийн байрлал) олохыг хүсэж байна.

Бид дахин дагаврын автоматыг байгуулна. Түүнчлэн бид автомат дахь бүх төлвийн хувьд $firstpos$ байрлалыг урьдчилан тооцоолно, өөрөөр хэлбэл төлөв $v$ бүрийн хувьд бид эхний орцын төгсгөлийн $firstpos[v]$ байрлалыг олохыг хүсэж байна. Өөрөөр хэлбэл бид $endpos$ олонлог бүрийн хамгийн бага элементийг урьдчилан олохыг хүсэж байна (учир нь бид бүх $endpos$ олонлогийг шууд хадгалж чадахгүй нь илэрхий).

Эдгээр $firstpos$ байрлалыг хадгалахын тулд бид sa_extend() функцийг өргөтгөнө. Шинэ төлөв $cur$ үүсгэх үед бид дараах байдлаар тохируулна:

$$firstpos(cur) = len(cur) - 1$$

Мөн $q$ оройг $clone$ болгон хувилах үед бид дараах байдлаар тохируулна:

$$firstpos(clone) = firstpos(q)$$

(учир нь утгын хувьд өөр цорын ганц сонголт нь $firstpos(cur)$ байх ба энэ нь мэдээж хэт том)

Ингэснээр асуулгын хариулт нь зүгээр л $firstpos(t) - length(P) + 1$ болно, энд $t$ нь $P$ тэмдэгт мөрд харгалзах төлөв юм. Асуулгад хариулахад дахин ердөө $O(length(P))$ хугацаа зарцуулна.

Бүх орцын байрлал

Энэ удаад бид $T$ тэмдэгт мөр дэх орцуудын бүх байрлалыг харуулах ёстой.

Бид дахин $T$ текстийн дагаврын автоматыг байгуулна. Өмнөх бодлогынхтой адилаар бид бүх төлвийн $firstpos$ байрлалыг тооцоолно.

Хэрэв $t$ нь асуулгын $P$ тэмдэгт мөрд харгалзах төлөв бол $firstpos(t)$ нь хариултын хэсэг байх нь тодорхой. Ингэснээр бид $P$-г агуулах автоматын төлвийг тооцлоо. Бид өөр ямар төлвүүдийг тооцох хэрэгтэй вэ? $P$ нь дагавар байх тэмдэгт мөрүүдэд харгалзах бүх төлвийг. Өөрөөр хэлбэл бид дагаврын холбоосоор дамжин $t$ төлөвт хүрч чадах бүх төлвийг олох хэрэгтэй.

Тиймээс бодлогыг бодохын тулд бид төлөв бүрийн хувьд түүн рүү хөтлөх дагаврын холбоосуудын жагсаалтыг хадгалах хэрэгтэй. Тэгвэл асуулгын хариулт нь $t$ төлвөөс эхлэн зөвхөн дагаврын холбоос ашиглан гүнзгийрүүлэх хайлт / өргөнөөр эхлэх хайлтаар олж болох төлөв бүрийн бүх $firstpos$-ыг агуулна.

Нийтдээ энэ нь урьдчилсан боловсруулалтад $O(length (T))$, хүсэлт бүрд $O(length(P) + answer(P))$ шаардана, энд $answer(P)$ — энэ нь хариултын хэмжээ юм.

Эхлээд бид эхлэх зангилаагаа олохын тулд хэв маяг дахь тэмдэгт бүрээр автоматаар доош явах ба энэ нь $O(length(P))$ шаардана. Дараа нь бид $O(answer(P))$ хугацаанд ажиллах шийдлээ ашиглана, учир нь бид нэг төлөвт хоёр удаа зочлохгүй (учир нь төлөв бүрээс ердөө нэг дагаврын холбоос гардаг тул нэг төлөв рүү хөтлөх хоёр өөр зам байж болохгүй).

Бид зөвхөн хоёр өөр төлөв ижил $firstpos$ утгатай байж болохыг тооцох ёстой. Энэ нь нэг төлөв нөгөөг нь хувилах замаар олдсон тохиолдолд болно. Гэвч энэ нь complexity-г эвдэхгүй, учир нь төлөв бүр хамгийн ихдээ ганц клонтой байж болно.

Түүнчлэн хэрэв бид хувилсан төлвүүдээс байрлалуудыг гаргахгүй бол давхардсан байрлалуудаас мөн салж чадна. Үнэндээ хувилсан төлөв хүрч чадах төлөвт анхны төлвөөс мөн хүрч болно. Тиймээс хэрэв бид төлөв бүрийн хувьд is_cloned флагийг санаж байвал бид хувилсан төлвүүдийг зүгээр л үл тоож, бусад бүх төлвийн $firstpos$-ыг л гаргаж чадна.

Хэрэгжүүлэлтийн зарим ноорог энд байна:

struct state {
    ...
    bool is_clone;
    int first_pos;
    vector<int> inv_link;
};

// after constructing the automaton
for (int v = 1; v < sz; v++) {
    st[st[v].link].inv_link.push_back(v);
}

// output all positions of occurrences
void output_all_occurrences(int v, int P_length) {
    if (!st[v].is_clone)
        cout << st[v].first_pos - P_length + 1 << endl;
    for (int u : st[v].inv_link)
        output_all_occurrences(u, P_length);
}

Гарч ирэхгүй хамгийн богино тэмдэгт мөр

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

Бид $S$ тэмдэгт мөрийн хувьд байгуулсан дагаврын автомат дээр динамик программчлал хэрэглэнэ.

$d[v]$ нь $v$ зангилааны хариулт байг, өөрөөр хэлбэл бид дэд мөрийн хэсгийг аль хэдийн боловсруулсан, одоо $v$ төлөвт байгаа бөгөөд оршин байхгүй шилжилтийг олохын тулд нэмэх шаардлагатай тэмдэгтийн хамгийн бага тоог олохыг хүсэж байна. $d[v]$-г тооцоолох нь маш энгийн. Хэрэв цагаан толгойн дор хаяж нэг тэмдэгтээр шилжилт байхгүй бол $d[v] = 1$. Эс бөгөөс нэг тэмдэгт хангалтгүй тул бид бүх шилжилтийн бүх хариултаас хамгийн багыг авах хэрэгтэй:

$$d[v] = 1 + \min_{w:(v,w,c) \in SA} d[w].$$

Бодлогын хариулт нь $d[t_0]$ байх ба бодит тэмдэгт мөрийг тооцоолсон $d[]$ массив ашиглан сэргээж болно.

Хоёр тэмдэгт мөрийн хамгийн урт нийтлэг дэд мөр

$S$ ба $T$ гэсэн хоёр тэмдэгт мөр өгөгдсөн. Бид хамгийн урт нийтлэг дэд мөрийг, өөрөөр хэлбэл $S$-д ба мөн $T$-д дэд мөр хэлбэрээр гарч ирэх $X$ тэмдэгт мөрийг олох ёстой.

Бид $S$ тэмдэгт мөрийн дагаврын автоматыг байгуулна.

Одоо бид $T$ тэмдэгт мөрийг аваад угтвар бүрийн хувьд тэр угтварын хамгийн урт дагаврыг $S$-ээс хайна. Өөрөөр хэлбэл $T$ тэмдэгт мөр дэх байрлал бүрийн хувьд бид тэр байрлалд төгсөх $S$ ба $T$-ийн хамгийн урт нийтлэг дэд мөрийг олохыг хүсэж байна.

Үүний тулд бид хоёр хувьсагч ашиглана: одоогийн төлөв $v$ ба одоогийн урт $l$. Эдгээр хоёр хувьсагч одоогийн таарч буй хэсгийг тодорхойлно: түүний урт ба түүнд харгалзах төлөв.

Эхэндээ $v = t_0$ ба $l = 0$, өөрөөр хэлбэл таарц хоосон байна.

Одоо бид $T[i]$ тэмдэгтийг хэрхэн нэмж, түүний хувьд хариултыг дахин тооцоолохыг тайлбарлая.

  • Хэрэв $v$-ээс $T[i]$ тэмдэгттэй шилжилт байвал бид зүгээр л шилжилтийг дагаад $l$-г нэгээр нэмэгдүүлнэ.
  • Хэрэв ийм шилжилт байхгүй бол бид одоогийн таарч буй хэсгийг богиносгох ёстой, өөрөөр хэлбэл бид дагаврын холбоосыг дагах хэрэгтэй: $v = link(v)$. Үүний зэрэгцээ одоогийн уртыг богиносгох ёстой. Бид $l = len(v)$ гэж оноох хэрэгтэй нь илэрхий, учир нь дагаврын холбоосоор дамжсаны дараа бид харгалзах хамгийн урт тэмдэгт мөр нь дэд мөр байх төлөвт очно.
  • Хэрэв шаардлагатай тэмдэгтээр шилжилт мөн л байхгүй бол бид шилжилт олох хүртэл эсвэл зохиомол төлөв $-1$-д хүрэх хүртэл давтан дахин дагаврын холбоосоор явж, $l$-г багасгана (энэ нь $T[i]$ тэмдэгт $S$-д огт гарч ирэхгүй гэсэн үг тул бид $v = l = 0$ гэж ононо).

Бодлогын хариулт нь бүх $l$ утгын хамгийн их нь байна.

Энэ хэсгийн complexity нь $O(length(T))$, учир нь нэг алхамд бид $l$-г нэгээр нэмэгдүүлэх, эсвэл дагаврын холбоосуудаар хэд хэдэн удаа явж болох ба тэдгээр бүр нь $l$ утгыг багасгаж дуусна.

Хэрэгжүүлэлт:

string lcs (string S, string T) {
    sa_init();
    for (int i = 0; i < S.size(); i++)
        sa_extend(S[i]);

    int v = 0, l = 0, best = 0, bestpos = 0;
    for (int i = 0; i < T.size(); i++) {
        while (v && !st[v].next.count(T[i])) {
            v = st[v].link ;
            l = st[v].len;
        }
        if (st[v].next.count(T[i])) {
            v = st [v].next[T[i]];
            l++;
        }
        if (l > best) {
            best = l;
            bestpos = i;
        }
    }
    return T.substr(bestpos - best + 1, best);
}

Олон тэмдэгт мөрийн хамгийн урт нийтлэг дэд мөр

$k$ ширхэг $S_i$ тэмдэгт мөр өгөгдсөн. Бид хамгийн урт нийтлэг дэд мөрийг, өөрөөр хэлбэл $S_i$ тэмдэгт мөр бүрд дэд мөр хэлбэрээр гарч ирэх $X$ тэмдэгт мөрийг олох ёстой.

Бид бүх тэмдэгт мөрийг нэг том $T$ тэмдэгт мөр болгон нийлүүлж, тэмдэгт мөрүүдийг тусгай $D_i$ тэмдэгтээр (тэмдэгт мөр бүрд нэг) тусгаарлана:

$$T = S_1 + D_1 + S_2 + D_2 + \dots + S_k + D_k.$$

Дараа нь бид $T$ тэмдэгт мөрийн дагаврын автоматыг байгуулна.

Одоо бид машинаас бүх $S_i$ тэмдэгт мөрд агуулагдах тэмдэгт мөрийг олох хэрэгтэй бөгөөд үүнийг нэмсэн тусгай тэмдэгтүүдийг ашиглан хийж болно. Хэрэв дэд мөр ямар нэг $S_j$ тэмдэгт мөрд агуулагдаж байвал дагаврын автоматад энэ дэд мөрөөс эхлэх, $D_j$ тэмдэгтийг агуулах бөгөөд бусад $D_1, \dots, D_{j-1}, D_{j+1}, \dots, D_k$ тэмдэгтүүдийг агуулахгүй зам байдгийг анхаарна уу.

Ингэснээр бид машины төлөв бүр ба $D_i$ тэмдэгт бүрийн хувьд ийм зам байгаа эсэхийг хэлж өгөх хүрэх боломжийг тооцоолох хэрэгтэй. Үүнийг гүнзгийрүүлэх хайлт эсвэл өргөнөөр эхлэх хайлт ба динамик программчлалаар хялбархан тооцоолж болно. Үүний дараа бодлогын хариулт нь бүх тусгай тэмдэгтийн хувьд зам байсан $v$ төлвийн $longest(v)$ тэмдэгт мөр байх болно.

Дасгал бодлогууд