Mavzu: Matnlar bilan ishlash z-funksiyasi Mundarija: Kirish i-bob. Z algaritmini qo’llash va ishlashi

2.3.Z algoritmiga misollar
Z algoritmi bilan taqqoslanadigan qatorlarni moslashtirish algoritmlari Rabin-Karp algoritmi, KMP algoritmi, sodda satrlarni moslashtirishdir .
Naive String qidiruv algoritmi uni har bir indeksda tekshiradigan naqshlarga mos keladi, Rabin Karp esa shunga o'xshash yondashuvga amal qiladi, lekin naqshga mos kelish uchun xesh funktsiyasidan foydalanadi.
KMP algoritmi Z algoritmiga o'xshash yondashuvni qo'llaydi , lekin u naqshning to'g'ri prefiksining eng uzun uzunligini saqlaydigan yordamchi massivdan foydalanadi, bu ham naqsh qo'shimchasi hisoblanadi.
Yuqoridagi jadvallarda biz sodda satrlarni moslashtirish va Rabin Karp algoritmlari juda katta vaqt murakkabligiga ega ekanligini ko'rishimiz mumkin va shuning uchun ularni katta kirishlar uchun ishlatishdan qochish kerak.
KMP algoritmi va Z algoritmi o'xshash vaqt murakkabligiga ega va bir-birining o'rnida ishlatilishi mumkin, ammo Z algoritmidan foydalanish afzalroq bo'lishi kerak, chunki kodlash va tushunish osonroq va hatto Z massivini disk raskadrovka qilish KMPda yordamchi massivni tuzatishdan ko'ra osonroqdir.
Z AlgoritmI
Uzunligi n bo'lgan S qator berilgan bo'lsa , Z algoritmi Z massivni hosil qiladi, bu erda Z [ i ] - S [ i ] dan boshlanuvchi eng uzun pastki qator uzunligi , bu ham S ning prefiksi , ya'ni maksimal k , shundayki S [ j ] = S [ i + j ] barcha 0 ≤ j < k uchun . E'tibor bering, Z [ i ] = 0 S [0] ≠ S ni bildiradi[ i ] . Terminologiyani osonlashtirish uchun biz pastki satrlarga murojaat qilamiz, ular ham prefiks-pastki qatorlar sifatida prefiks hisoblanadi.

Algoritm yagona, hal qiluvchi invariantga tayanadi. Satrdagi harflar ustida takrorlanganda (indeks i 1 dan n - 1 gacha ) , biz maksimal R ga ega bo'lgan intervalni [ L , R ] oraliqda saqlaymiz , shunda 1 ≤ L ≤ i ≤ R va S [ L . .. R ] prefiks-pastki qatordir (agar bunday oraliq bo'lmasa, L = R = - 1 bo'lsin ). i = 1 uchun L ni oddiygina hisoblashimiz mumkinva S [ 0 ...] ni S [1...] ga solishtirish orqali R. Bundan tashqari, biz Z [1] ni ham olamiz .

Endi bizda i - 1 va i - 1 gacha bo'lgan barcha Z qiymatlari uchun to'g'ri interval [ L , R ] bor, deylik . Biz Z [ i ] va yangi [ L , R ] ni quyidagi bosqichlar orqali hisoblaymiz :

Agar i > R bo'lsa, i dan oldin boshlanuvchi va i da yoki keyin tugaydigan S ning prefiks-pastki qatori mavjud emas . Agar shunday pastki qator mavjud bo'lsa, [ L , R ] uning joriy qiymati emas, balki ushbu pastki qator uchun interval bo'lar edi. Shunday qilib, biz S [0...] ni S [ i ...] bilan taqqoslash orqali yangi [ L , R ] ni "qayta o'rnatamiz" va hisoblaymiz va bir vaqtning o'zida Z [ i ] ni olamiz ( Z [ i ] = R - L + 1 ).
Aks holda, i ≤ R , shuning uchun oqim [ L , R ] kamida i ga cho'ziladi . k = i - L bo'lsin . Biz bilamizki, Z [ i ] ≥ min ( Z [ k ], R - i + 1) , chunki S [ i ...] kamida R - i + 1 ta belgi uchun S [ k ...] ga mos keladi (ular ichida [ _L , R ] oralig'i biz prefiks-pastki qator deb bilamiz). Endi bizda yana bir nechta holatlar bor.
Agar Z [ k ] < R - i + 1 bo'lsa, S [ i ] dan boshlanadigan prefiks-pastki qator yo'q (yoki aks holda Z [ k ] kattaroq bo'lar edi, ya'ni Z [ i ] = Z [ k ] va [ L , R ] bir xil bo'lib qoladi. Ikkinchisi to'g'ri, chunki [ L , R ] faqat S [ i ] dan boshlanadigan prefiks-pastki qator mavjud bo'lganda o'zgaradi.bu R dan tashqariga chiqadi , biz bilamizki, bu erda bunday emas.
Agar Z [ k ] ≥ R - i + 1 bo'lsa, u holda S [ i ...] ga R - i + 1 dan ortiq belgilar (ya'ni o'tgan R pozitsiyasi) uchun S [0...] mos kelishi mumkin . Shunday qilib, biz yangi R ni olish uchun L = i o'rnatish va S [ R + 1] dan oldinga mos kelish orqali [ L , R ] ni yangilashimiz kerak . Yana Z [ i ] ni olamizbu vaqtda.
Jarayon barcha Z qiymatlarini qatordan bir marta o'tishda hisoblab chiqadi, shuning uchun biz tugatdik. To'g'rilik algoritmga xosdir va juda intuitiv tarzda aniq.

Tahlil
Biz algoritm O ( n ) vaqtida ishlaydi va argument to'g'ridan-to'g'ri ekanligini da'vo qilamiz. Biz hech qachon R dan kichik oʻrinlarda belgilarni solishtirmaymiz va har safar mos kelganda R belgisi bittaga ortadi, shuning uchun u yerda koʻpi bilan n ta taqqoslash mumkin. Nihoyat, biz har bir i uchun faqat bir marta mos kelmasligimiz mumkin (bu R o'sishni to'xtatadi), shuning uchun bu ko'pi bilan n ta taqqoslash bo'lib, O ( n ) jami beradi .

Kod
Oddiy va qisqa. E'tibor bering, optimallashtirish L = R = i S [0] ≠ S [ i ] bo'lganda qo'llaniladi (bu algoritmga ta'sir qilmaydi, chunki keyingi iteratsiyada i > R bo'lishidan qat'i nazar).

int L = 0, R = 0;

uchun (int i = 1; i < n; i++) {
agar (i > R) {
L = R = i;
esa (R < n && s[RL] == s[R]) R++;
z[i] = RL; R--;
} boshqa {
int k = iL;
agar (z[k] < R-i+1) z[i] = z[k];
boshqa {
L = i;
esa (R < n && s[RL] == s[R]) R++;
z[i] = RL; R--;
}
}
}

Ilova
Z algoritmining bir qo'llanilishi n uzunlikdagi S satrda m uzunlikdagi T naqsh uchun mosliklarni topishning standart satr moslash muammosi uchundir . Buni O ( n + m ) vaqtida T PH S satrida Z algoritmidan foydalanib (ya’ni T , PH va S ni birlashtirish ) amalga oshirishimiz mumkin , bunda p hech narsaga mos kelmaydigan belgidir. Z [ i ] = m bo'lgan i indekslari T ning mosliklariga mos keladi S ichida .

Nihoyat, 93-raundning beta-raundining B muammosini hal qilish uchun biz berilgan S qator uchun Z ni hisoblaymiz , keyin i dan n - 1 gacha takrorlaymiz . Agar Z [ i ] = n - i bo'lsa, biz S [ i ] qo'shimchasi prefiks ekanligini bilamiz va agar biz hozirgacha ko'rgan eng katta Z qiymati kamida n - i bo'lsa , unda biz ichidagi ba'zi qatorlar ham mos kelishini bilamiz. bu prefiks. Bu natija beradi.

int maxz = 0, res = 0;

uchun (int i = 1; i < n; i++) {
agar (z[i] == ni && maxz >= ni) { res = ni; sindirish; }
maxz = max(maxz, z[i]);