Z-функц ба түүнийг тооцоолох¶

$n$ урттай $s$ тэмдэгт мөр өгөгдсөн гэж үзье. Энэ тэмдэгт мөрийн Z-функц гэдэг нь $n$ урттай массив бөгөөд $i$ дахь элемент нь $i$ байрлалаас эхлэн $s$-ийн эхний тэмдэгтүүдтэй давхцах тэмдэгтийн хамгийн их тоотой тэнцүү байна.

Өөрөөр хэлбэл $z[i]$ нь $s$-ийн угтвар бөгөөд нэгэн зэрэг $i$-ээс эхлэх $s$-ийн дагаврын угтвар байх хамгийн урт тэмдэгт мөрийн урт юм.

Тэмдэглэл. Энэ өгүүлэлд хоёрдмол утга гарахаас зайлсхийхийн тулд бид $0$-ээс эхлэх индексжүүлэлт ашиглана; өөрөөр хэлбэл $s$-ийн эхний тэмдэгт $0$ индекстэй, сүүлийнх нь $n-1$ индекстэй байна.

Z-функцийн эхний элемент $z[0]$ нь ерөнхийдөө сайн тодорхойлогдоогүй. Энэ өгүүлэлд бид түүнийг тэг гэж үзнэ (хэдийгээр энэ нь алгоритмын хэрэгжүүлэлтэд юу ч өөрчлөхгүй).

Энэ өгүүлэлд Z-функцийг $O(n)$ хугацаанд тооцоолох алгоритм, мөн түүний төрөл бүрийн хэрэглээг танилцуулна.

Жишээ¶

Жишээ нь өөр өөр тэмдэгт мөрийн хувьд тооцоолсон Z-функцийн утгууд энд байна:

"aaaaa" - $[0, 4, 3, 2, 1]$
"aaabaab" - $[0, 2, 1, 0, 2, 1, 0]$
"abacaba" - $[0, 0, 1, 0, 3, 0, 1]$

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

Албан ёсны тодорхойлолтыг дараах энгийн $O(n^2)$ хэрэгжүүлэлтээр илэрхийлж болно.

vector<int> z_function_trivial(string s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1; i < n; i++) {
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
    }
    return z;
}

Бид зүгээр л байрлал $i$ бүрийг гүйж, тус бүрийн хувьд $z[i] = 0$-ээс эхлэн, таарахгүй байдал олохгүй байх хооронд (мөн мөрийн төгсгөлд хүрэхгүй байх хооронд) $z[i]$-г нэмэгдүүлэн шинэчилнэ.

Мэдээж энэ бол үр ашигтай хэрэгжүүлэлт биш. Одоо бид үр ашигтай хэрэгжүүлэлтийг хэрхэн байгуулахыг үзүүлнэ.

Z-функцийг тооцоолох үр ашигтай алгоритм¶

Үр ашигтай алгоритм авахын тулд бид $z[i]$-ийн утгыг $i = 1$-ээс $n - 1$ хүртэл дараалан тооцоолох ба үүний зэрэгцээ шинэ утга тооцоолохдоо өмнө тооцоолсон утгуудыг аль болох сайн ашиглахыг оролдоно.

Товчхон байх үүднээс $s$-ийн угтвартай давхцах дэд мөрүүдийг хэрчмийн таарц гэж нэрлэе. Жишээ нь хүссэн Z-функц $z[i]$-ийн утга нь $i$ байрлалаас эхэлж ($i + z[i] - 1$ байрлалд дуусах) хэрчмийн таарцын урт юм.

Үүний тулд бид хамгийн баруун хэрчмийн таарцын $[l, r)$ индексүүдийг хадгална. Өөрөөр хэлбэл илрүүлсэн бүх хэрчмээс хамгийн баруун талд дуусахыг нь хадгална. Тодорхой утгаараа $r$ индексийг алгоритм бидний $s$ тэмдэгт мөрийг хаана хүртэл сканнердсаныг заах "хязгаар" гэж үзэж болно; тэр цэгээс цаашхи бүх зүйл хараахан мэдэгдээгүй.

Тэгвэл хэрэв одоогийн индекс (түүний хувьд бид Z-функцийн дараагийн утгыг тооцоолох ёстой) нь $i$ бол бидэнд хоёр сонголтын нэг байна:

$i \geq r$ -- одоогийн байрлал бидний аль хэдийн боловсруулсан зүйлийн гадна байна.

Тэгвэл бид $z[i]$-г тривиаль алгоритмаар тооцоолно (өөрөөр хэлбэл утгуудыг зүгээр л нэг нэгээр нь харьцуулна). Эцэст нь хэрэв $z[i] > 0$ бол бид хамгийн баруун хэрчмийн индексүүдийг шинэчлэх шаардлагатай болохыг анзаар, учир нь шинэ $r = i + z[i]$ нь өмнөх $r$-ээс сайн байх нь баталгаатай.
$i < r$ -- одоогийн байрлал одоогийн $[l, r)$ хэрчмийн таарцын дотор байна.

Тэгвэл бид аль хэдийн тооцоолсон Z-утгуудыг ашиглан $z[i]$-ийн утгыг ямар нэг зүйлээр "эхлүүлж" болно (энэ нь "тэгээс эхлэхээс" илүү сайн нь лавтай), магадгүй бүр ямар нэг том тоогоор.

Үүний тулд бид $s[l \dots r)$ ба $s[0 \dots r-l)$ дэд мөрүүд таарч байгааг ажиглана. Энэ нь $z[i]$-ийн эхний ойролцоолол болгон бид харгалзах $s[0 \dots r-l)$ хэрчмийн хувьд аль хэдийн тооцоолсон утга буюу $z[i-l]$-г авч болно гэсэн үг юм.

Гэвч $z[i-l]$ утга хэтэрхий том байж болно: $i$ байрлалд хэрэглэхэд энэ нь $r$ индексээс хэтэрч болно. Энэ нь зөвшөөрөгдөхгүй, учир нь бид $r$-ээс баруун талын тэмдэгтүүдийн тухай юу ч мэдэхгүй: тэдгээр нь шаардагдахаас өөр байж болно.

Ижил төстэй хувилбарын жишээ энд байна:

$$ s = "aaaabaa" $$

Бид сүүлийн байрлалд ($i = 6$) хүрэхэд одоогийн таарцын хэрчим нь $[5, 7)$ байна. Тэгвэл байрлал $6$ нь байрлал $6 - 5 = 1$-тэй таарах ба түүний хувьд Z-функцийн утга нь $z[1] = 3$ юм. Бид $z[6]$-г $3$-аар эхлүүлж чадахгүй нь илэрхий, энэ нь бүрэн буруу байх болно. Бидний эхлүүлж болох хамгийн их утга нь $1$ юм -- учир нь энэ бол биднийг $[l, r)$ таарцын хэрчмийн $r$ индексээс цааш аваачихгүй хамгийн том утга юм.

Тиймээс $z[i]$-ийн эхний ойролцоолол болгон бид дараахыг аюулгүйгээр авч болно:

$$ z_0[i] = \min(r - i,\; z[i-l]) $$

$z[i]$-г $z_0[i]$-ээр эхлүүлсний дараа бид тривиаль алгоритмыг ажиллуулж $z[i]$-г нэмэгдүүлэхийг оролдоно -- учир нь ерөнхийдөө $r$ хязгаараас цааш хэрчим таарсаар байх эсэхийг бид мэдэж чадахгүй.

Ингэснээр бүхэл алгоритм хоёр тохиолдолд хуваагдах ба тэдгээр нь зөвхөн $z[i]$-ийн эхний утгаараа ялгаатай: эхний тохиолдолд түүнийг тэг гэж үзэх ба хоёр дахь тохиолдолд өмнө тооцоолсон утгуудаар (дээрх томьёог ашиглан) тодорхойлогдоно. Үүний дараа энэ алгоритмын хоёр салаа хоёулаа эхний утгыг зааж өгсний дараа шууд эхлэх тривиаль алгоритмын хэрэгжүүлэлт болж хураагдана.

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

Implementation¶

Implementation turns out to be rather concise:

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

Comments on this implementation¶

The whole solution is given as a function which returns an array of length $n$ -- the Z-function of $s$.

Array $z$ is initially filled with zeros. The current rightmost match segment is assumed to be $[0; 0)$ (that is, a deliberately small segment which doesn't contain any $i$).

Inside the loop for $i = 1 \dots n - 1$ we first determine the initial value $z[i]$ -- it will either remain zero or be computed using the above formula.

Thereafter, the trivial algorithm attempts to increase the value of $z[i]$ as much as possible.

In the end, if it's required (that is, if $i + z[i] > r$), we update the rightmost match segment $[l, r)$.

Алгоритмын асимптот зан төлөв¶

Бид дээрх алгоритмын ажиллах хугацаа тэмдэгт мөрийн уртаас шугаман хамааралтай буюу $O(n)$ болохыг батлана.

Баталгаа нь маш энгийн.

Бид үүрлэсэн while давталтыг сонирхож байна, учир нь бусад бүх зүйл нь нийлээд $O(n)$ болох тогтмол үйлдлүүдийн багц юм.

Бид while давталтын давталт бүр таарцын хэрчмийн баруун хязгаар $r$-г нэмэгдүүлэхийг үзүүлнэ.

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

$i \geq r$

Энэ тохиолдолд while давталт ямар ч давталт хийхгүй (хэрэв $s[0] \ne s[i]$ бол), эсвэл $i$ байрлалаас эхлэн, тухай бүр нэг тэмдэгт баруун тийш шилжин хэдэн давталт хийнэ. Үүний дараа баруун хязгаар $r$ зайлшгүй шинэчлэгдэнэ.

Тиймээс бид $i \geq r$ үед while давталтын давталт бүр шинэ $r$ индексийн утгыг нэмэгдүүлдгийг оллоо.
$i < r$

Энэ тохиолдолд бид $z[i]$-г дээрх томьёогоор өгөгдсөн тодорхой $z_0$ утгаар эхлүүлнэ. Энэ эхний утга $z_0$-г $r - i$ утгатай харьцуулъя. Бидэнд гурван тохиолдол байна:
- $z_0 < r - i$
  
  Энэ тохиолдолд while давталтын ямар ч давталт хийгдэхгүйг бид батална.
  
  Үүнийг жишээ нь зөрчлөөр батлахад амархан: хэрэв while давталт дор хаяж нэг давталт хийсэн бол энэ нь эхний ойролцоолол $z[i] = z_0$ нь буруу байсан (таарцын бодит уртаас бага) гэсэн үг болно. Гэвч $s[l \dots r)$ ба $s[0 \dots r-l)$ ижил тул энэ нь $z[i-l]$ буруу утга (байх ёстойгоос бага) агуулж байна гэсэн үг болно.
  
  Тиймээс $z[i-l]$ зөв бөгөөд $r - i$-ээс бага тул энэ утга шаардагдах $z[i]$ утгатай давхцаж байна гэж гарна.
- $z_0 = r - i$
  
  Энэ тохиолдолд while давталт хэдэн давталт хийж болох ч тэдгээр тус бүр $r$ индексийн утгыг нэмэгдүүлэхэд хүргэнэ, учир нь бид $s[r]$-ээс харьцуулж эхлэх ба энэ нь $[l, r)$ интервалаас цааш гарна.
- $z_0 > r - i$
  
  $z_0$-ийн тодорхойлолтоор энэ хувилбар боломжгүй.

Тиймээс бид дотоод давталтын давталт бүр $r$ заагчийг баруун тийш ахиулдгийг баталлаа. $r$ нь $n-1$-ээс их байж чадахгүй тул энэ нь дотоод давталт $n-1$-ээс олон давталт хийхгүй гэсэн үг юм.

Алгоритмын бусад хэсэг илэрхий $O(n)$-д ажилладаг тул бид Z-функц тооцоолох бүхэл алгоритм шугаман хугацаанд ажилладгийг баталлаа.

Хэрэглээ¶

Одоо бид Z-функцийн тодорхой бодлогод хэрэглэгдэх зарим хэрэглээг авч үзнэ.

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

Дэд мөр хайх¶

Будлиан гарахаас зайлсхийхийн тулд бид $t$-г текстийн тэмдэгт мөр, $p$-г хэв маяг гэж нэрлэнэ. Бодлого нь: $t$ текст доторх $p$ хэв маягийн бүх орцыг ол.

Энэ бодлогыг бодохын тулд бид $s = p + \diamond + t$ шинэ тэмдэгт мөр үүсгэнэ, өөрөөр хэлбэл бид $p$ ба $t$-д тэмдэгт мөрийн залгалт хэрэглэх боловч дунд нь $\diamond$ тусгаарлагч тэмдэгт мөн тавина ($\diamond$-г $p$ буюу $t$ тэмдэгт мөрийн хаана ч байхгүй байхаар сонгоно).

$s$-ийн Z-функцийг тооцоол. Дараа нь $[0; \; \operatorname{length}(t) - 1]$ интервал дахь дурын $i$-ийн хувьд бид харгалзах $k = z[i + \operatorname{length}(p) + 1]$ утгыг авч үзнэ. Хэрэв $k$ нь $\operatorname{length}(p)$-тэй тэнцүү бол $t$-ийн $i$ дахь байрлалд $p$-ийн нэг орц байгааг бид мэднэ, эс бөгөөс $t$-ийн $i$ дахь байрлалд $p$-ийн орц байхгүй.

Ажиллах хугацаа (ба санах ойн хэрэглээ) нь $O(\operatorname{length}(t) + \operatorname{length}(p))$ юм.

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

$n$ урттай $s$ тэмдэгт мөр өгөгдсөн үед $s$-ийн ялгаатай дэд мөрийн тоог тоол.

Бид энэ бодлогыг давталттайгаар бодно. Өөрөөр хэлбэл: ялгаатай дэд мөрийн одоогийн тоог мэдэж байгаад $s$-ийн төгсгөлд нэг тэмдэгт нэмсний дараа энэ тоог дахин тооцоолно.

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

$t = s + c$ тэмдэгт мөрийг аваад түүнийг урвуул (түүний тэмдэгтүүдийг урвуу дарааллаар бич). Бидний бодлого одоо $t$-ийн хэдэн угтвар $t$-ийн өөр хаана ч олдохгүй байгааг тоолох явдал юм. $t$-ийн Z-функцийг тооцоолж, түүний хамгийн их утга $z_{max}$-г олъё. $t$-ийн $z_{max}$ урттай угтвар мөн $t$-ийн дунд хаа нэгтээ гарч ирэх нь илэрхий. Илүү богино угтварууд ч мөн гарч ирэх нь ойлгомжтой.

Тиймээс $s$-д $c$ тэмдэгт залгах үед гарч ирэх шинэ дэд мөрийн тоо $\operatorname{length}(t) - z_{max}$-тэй тэнцүү болохыг бид оллоо.

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

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

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

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

Шийдэл нь: $s$-ийн Z-функцийг тооцоолж, $i$ нь $n$-г хуваах бүх $i$-г гүй. $i + z[i] = n$ байх эхний $i$ дээр зогс. Тэгвэл $s$ тэмдэгт мөрийг $i$ урт хүртэл шахаж болно.

Энэ баримтын баталгаа нь угтвар функц-ийг ашигладаг шийдэлтэй ижил.