Prefiks funksiyasi, uni hisoblash va qo‘lash. knut-moriss-pratt algoritmi

Информация о документе

Цена	12000UZS
Размер	459.8KB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Дипломные работы
Предмет	Информатика и ИТ

Prefiks funksiyasi, uni hisoblash va qo‘lash. knut-moriss-pratt algoritmi

Купить

KIRISH
Informatika sohasida Knuth-Morris-Pratt string-qidiruv algoritmi (yoki KMP
algoritmi) mos kelmaslik yuzaga kelganda so'zning o'zini o'zida
mujassamlashtirganini kuzatish orqali asosiy "matn qatori" S ichida "so'z" W ning
paydo bo'lishini qidiradi. keyingi o'yin qaerda boshlanishi mumkinligini aniqlash
uchun etarli ma'lumot, shu bilan avval mos keladigan belgilarni qayta tekshirishni
chetlab o'tadi. Algoritm Jeyms X. Morris tomonidan ishlab chiqilgan va mustaqil
ravishda Donald Knut tomonidan avtomatlar nazariyasidan "bir necha hafta
o'tgach" kashf etilgan.[1][2] Morris va Vogan Pratt 1970 yilda texnik hisobotni
chop etishdi.[3] 1977-yilda uchtasi algoritmni birgalikda nashr etishgan.[1]
Mustaqil ravishda, 1969 yilda Matiyasevich[4][5] ikkilik alifboda satr-naqsh mos
keladigan aniqlash masalasini o'rganayotganda ikki o'lchovli Tyuring mashinasi
tomonidan kodlangan shunga o'xshash algoritmni kashf etdi. Bu satrlarni
moslashtirish uchun birinchi chiziqli vaqt algoritmi edi. Algoritm 1970 yilda
Donald Knut va Vogan Pratt tomonidan va mustaqil ravishda Jeyms X. Morris
tomonidan ishlab chiqilgan. 1977 yilda uchtasi birgalikda nashr etishgan. KMP
usuli izlanayotgan satrni oldindan qayta ishlashdan foydalanadi, ya’ni uning
asosida prefiks funksiya yaratiladi. Bunda quyidagi g’oyadan foydalaniladi. Agar i
uzulikdagi so’z prefiksi (u ham suffiks) bitta simvolga uzun bo’lsa, u holda bir
vaqtda i-1 uzunlikdan qism satr prefiksi ham bo’ladi.
Shunday qilib, biz oldingi qism satr prefiksini tekshiramiz. Agar u to’g’ri
kelmasa, u holda uning prefiksining prefiksini tekshiramiz va hakozo. Shunday ish
yuritib, eng katta izlanayotgan prefiksni topamiz. Navbatdagi savol: nima uchun
prosedura ish vaqti chiziqli, unda ichki joylashgan sikl borku? Bizga undan
prefiks-funksiyani berish m marta ro’y beradi, qolgan vaqtda k o’zgaruvchi
o’zgaradi. while siklda u(P[k]<k) ga kamaygan, lekin noldan kichkina bo’lmagani
uchun shunga qaraganda kam bo’lmagan marta kamayishi mumkin. K o’zgaruvchi
birga m dan ko’p bo’lmagan marta o’sadi. Demak, k o’zgaruvchi jami ikki
martadan ko’p bo’lmagan holda o’zgaradi. Bunday butun prosedura ish vaqti
O( m) ga teng [7,8]. Haqiqiy dunyoda KMP algoritmi naqshlarni moslashtirish uzun
satrlarda amalga oshiriladigan ilovalarda qo'llaniladi, ularning belgilari kichik
alifbodan olingan. Tegishli misol - faqat 4 ta belgidan (A, C, G, T) iborat DNK
alifbosi. s qatori uchun prefiks funktsiyasi s ning eng uzun to'g'ri prefiksi uzunligi
sifatida aniqlanadi, bu ham s ning qo'shimchasi hisoblanadi. To'g'ri (men uni
kursivlashni to'xtataman) prefiksi s ning o'zi bo'lmagan har qanday s prefiksi, ya'ni
s ning har qanday prefiksidir.
2

I-BOB. PREFIKS FUNKTSIYASI, UNI HISOBLASH VA
QO’LLANILISH
1.1.Prefiks funktsiyasi ta'rifi
Sizga n uzunlikdagi s qator berilgan. Ushbu qator uchun prefiks funksiyasi n
uzunlikdagi p massiv sifatida aniqlanadi, bu erda π[i] s[0…i] pastki satrining eng
uzun tegishli prefiksining uzunligi, u ham ushbu pastki qatorning qo'shimchasi
hisoblanadi. Satrning to'g'ri prefiksi qatorning o'ziga teng bo'lmagan prefiksdir.
Ta rifi bo yicha π[0]=0. Prefiks funktsiyasining matematik ta'rifi quyidagichaʼ ʻ
yozilishi mumkin:
Masalan, "abcabcd" qatorining prefiks funksiyasi [0,0,0,1,2,3,0] va "aabaaab"
qatorining prefiks funksiyasi [0,1,0,1,2,2,3 ].
Prefiks funktsiyasi s satrining prefiks funktsiyasi π massivga teng, bu erda π [i] s
[0..i] satrning uning qo'shimchasiga mos keladigan maksimal prefiksi uzunligini
bildiradi. Arzimas holatlar (prefiks qo'shimchaga teng va butun satrga teng)
hisobga olinmaydi.
3

$1-rasm. Rasmda uzunligi ushbu pozitsiyadagi prefiks funktsiyasi qiymatiga teng bo'lgan teng pastki qatorlar ko'rsatilgan. Butun “abacaba” qatori uchun prefiks funksiyasi: {0,0,1,0,1,2,3}. π [0] = π [1] = 0, chunki “a” va “ab” satrlari ahamiyatsiz va shuning uchun hisobga olinmaydi. Ba'zi hollarda prefiks va qo'shimchalar bir-biriga mos kelishi mumkin: 2-rasm. Prefiks funktsiyasini topish uchun sodda algoritm O (N 3 ) murakkabligiga ega, bu ko'p hollarda qabul qilinishi mumkin emas. Juda ham samarali O (N) algoritmi mavjud. Amalga oshirish: vector<int> prefix_function(const string& s) { vector<int> pi(s.length(), 0); for (int i = 1; i < s.length(); i++) { int j = pi[i - 1]; //biz davom ettirmoqchi bo'lgan prefiksning joriy uzunligi //s [0..j-1] = s [i-j..i-1] bo lishi kafolatlanadi.ʻ while (j > 0 && s[i] != s[j]) { //joriy prefiks bilan davom etgunimizcha j = pi[j - 1]; // uning uzunligini iloji boricha qisqartiring } //Endi j - biz davom ettirishimiz mumkin bo'lgan prefiksning maksimal uzunligi, 4$ $//yoki hech biri mavjud bo'lmasa 0. if (s[i] == s[j]) { pi[i] = j + 1; } else { //Bu faqat j = 0 uchun sodir bo'lishi mumkin pi[i] = j; } } return pi; } 1.2.Prefiks funktsiyasidan foydalanishga misollar Prefiks funktsiyasi juda kuchli tuzilma bo'lib, u satr muammolarining muhim qismini hal qilish uchun ishlatilishi mumkin. Prefiks funksiyasining klassik muammosi qatordagi pastki qatorni topish muammosidir (KMP algoritmi dastlab ushbu muammoni hal qilish uchun maxsus ishlab chiqilgan). Keling, buni misol sifatida ko'rib chiqaylik. Faraz qilaylik, s satrida t pastki qatorni topishimiz kerak. Prefiks funktsiyasi yordamida bu arzimas tarzda amalga oshiriladi: biz t + # + s qatoridan prefiks funktsiyasini topamiz (xesh hech qanday satrda ko'rinmasligi kafolatlangan belgini bildiradi). Agar ushbu prefiks funktsiyasi t uzunligiga teng qiymatlarni o'z ichiga olsa, u holda t s tarkibiga kiradi. Ya'ni, π [i] = | t | bo'lsin. Demak, s [i− | t | −1] t ning s ichida yuzaga kelishining oxirgi belgisidir. C ++ da qo’llanilish: #include <bits/stdc++.h> using namespace std; vector<int> prefix_function(const string& s) { vector<int> pi(s.length(), 0); for (int i = 1; i < s.length(); i++) { int j = pi[i - 1]; while (j > 0 && s[i] != s[j]) { j = pi[j - 1]; } 5$ $if (s[i] == s[j]) { pi[i] = j + 1; } else { pi[i] = j; } } return pi; } int main() { string s, t; cin >> s >> t; vector<int> pi = prefix_function(t + '#' + s); int t_len = t.length(); for (int i = 0; i < s.length(); i++) { if (pi[t_len + 1 + i] == t_len) { cout << "s[" << i - t_len + 1 << ".." << i << "] = t" << endl; } } } Kiritish: Salom Salom Natija: Oddiy algoritm Prefiks funktsiyasi ta'rifiga to'liq mos keladigan algoritm quyidagicha: 6$ $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; } Uning murakkabligi O(n 3 )O(n 3 ) ekanligini ko‘rish oson, bunda yaxshilash uchun joy bor. Samarali algoritm Bu algoritm 1977 yilda Knut va Pratt tomonidan taklif qilingan va ulardan mustaqil ravishda Morris tomonidan 1977 yilda taklif qilingan. U pastki qatorni qidirish algoritmining asosiy funktsiyasi sifatida ishlatilgan. Birinchi optimallashtirish Birinchi muhim kuzatish shundan iboratki, prefiks funktsiyasi qiymatlari faqat bittaga ko'payishi mumkin. Darhaqiqat, aks holda, agar π [i+1]> π [i]+1 bo'lsa, u holda biz π [i+1] uzunlikdagi i+1 pozitsiyasida tugaydigan ushbu qo'shimchani olib, undan oxirgi belgini olib tashlashimiz mumkin. Biz π [i+1]-1 uzunlikdagi i pozitsiyasida tugaydigan qo'shimcha bilan yakunlaymiz, bu π [i] dan yaxshiroq, ya'ni qarama-qarshilikni olamiz. Quyidagi rasm bu qarama-qarshilikni ko'rsatadi. Prefiks bo‘lgan i pozitsiyadagi eng uzun to‘g‘ri qo‘shimchaning uzunligi 2, i+1 pozitsiyasida esa 4 uzunligi. Shuning uchun s0 s1 s2 s3 qatori si−2 si−1 si si+ qatoriga teng. 1, ya’ni s0 s1 s2 va si−2 si−1 si qatorlari ham teng, shuning uchun π [i] 3 bo‘lishi kerak. 7$

3-rasm.
Shunday qilib, keyingi pozitsiyaga o'tayotganda, prefiks funktsiyasining qiymati
bittaga oshishi, o'zgarmasligi yoki biroz kamayishi mumkin. Bu fakt allaqachon
algoritmning murakkabligini O(n2) ga kamaytirishga imkon beradi, chunki bir
qadamda prefiks funksiyasi ko'pi bilan bittaga o'sishi mumkin. Jami funktsiya eng
ko'p n bosqichda o'sishi mumkin va shuning uchun ham faqat n ta qadam
kamayishi mumkin. Bu shuni anglatadiki, biz faqat O(n) qatorni taqqoslashimiz va
O(n2) murakkabligiga erishishimiz kerak.
Ikkinchi optimallashtirish
Keling, oldinga boraylik, biz chiziqli taqqoslashlardan xalos bo'lishni xohlaymiz.
Buni amalga oshirish uchun biz oldingi bosqichlarda hisoblangan barcha
ma'lumotlardan foydalanishimiz kerak.
Shunday qilib, i+1 uchun π prefiks funksiyasining qiymatini hisoblaymiz. Agar
s[i+1]=s[π[i]] bo'lsa, biz aniqlik bilan π[i+1]= π[i]+1 deb aytishimiz mumkin,
chunki biz allaqachon bilamizki, i holatidagi qo'shimcha uzunlikdagi π[i]
uzunlikdagi π[i] prefiksiga teng. Bu yana bir misol bilan ko'rsatilgan.
4-rasm.
Agar bunday bo'lmasa, s[i+1]≠s[π[i]], u holda biz qisqaroq qatorni sinab
ko'rishimiz kerak. Ishni tezlashtirish uchun biz zudlik bilan j<π[i] eng uzun
uzunlikka o'tmoqchimiz, shundayki i pozitsiyasida prefiks xususiyati, ya'ni s[0…
j−1]=s[i−j +1…i]:
5-rasm.
Haqiqatan ham, agar shunday j uzunlikni topsak, u holda biz yana faqat s[i+1] va
s[j] belgilarini solishtirishimiz kerak. Agar ular teng bo'lsa, π[i+1]=j+1 ni
8

belgilashimiz mumkin. Aks holda biz j dan kichikroq eng katta qiymatni
topishimiz kerak bo'ladi, buning uchun prefiks xossasi mavjud va hokazo. Bu j=0
gacha davom etishi mumkin. Agar u holda s[i+1]=s[0] bo'lsa, π[i+1]=1, aks holda
π[i+1]=0 ni belgilaymiz. Shunday qilib, bizda allaqachon algoritmning umumiy
sxemasi mavjud. Qolgan yagona savol - j uchun uzunliklarni qanday qilib samarali
topishimiz. Keling, takrorlaymiz: joriy j uzunligi uchun prefiks xossasi mavjud
bo'lgan i holatida, ya'ni s[0…j−1]=s[i−j+1…i], biz eng katta k<j ni topmoqchimiz,
ular uchun prefiks xususiyati mavjud.
6-rasm.
Rasm shuni ko'rsatadiki, bu biz ilgari hisoblagan π[j−1] qiymati bo'lishi kerak.
Yakuniy algoritm
Shunday qilib, biz oxir-oqibat hech qanday satrlarni taqqoslamaydigan va faqat
O(n) amallarni bajaradigan algoritmni yaratishimiz mumkin.
Mana yakuniy protsedura:
 Biz i=1 dan i=n−1 gacha takrorlash orqali siklda π [i] prefiks qiymatlarini
hisoblaymiz ( π [0] shunchaki 0 bilan tayinlanadi).
 Joriy qiymatni hisoblash uchun π [i] i-1 uchun eng yaxshi qo'shimchaning
uzunligini bildiruvchi j o'zgaruvchisini o'rnatamiz. Dastlab j= π [i−1].
 Uzunlikdagi j+1 qo‘shimchasi ham prefiks ekanligini s[j] va s[i] ni
solishtirish orqali tekshiring. Agar ular teng bo'lsa, biz π [i]=j+1 ni
belgilaymiz, aks holda j ni π [j−1] ga qisqartiramiz va bu amalni
takrorlaymiz.
 Agar biz j=0 uzunlikka yetgan bo‘lsak va hali ham mos kelmasak, u holda
π [i]=0 ni belgilaymiz va keyingi indeksga i+1 o‘tamiz.
Amalga oshirish
Amalga oshirish hayratlanarli darajada qisqa va ifodali bo'lib tugaydi.
9

$prefix_function( string s) { int n = ( int )s.length(); vector<int> pi(n); for ( vector<int> 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; } Bu onlayn algoritmdir, ya'ni ma'lumotlarni kelishi bilan qayta ishlaydi - masalan, satr belgilarini birma-bir o'qib, har bir keyingi belgi uchun prefiks funktsiyasi qiymatini topib, ularni darhol qayta ishlashingiz mumkin. Algoritm hali ham satrning o'zini va prefiks funktsiyasining oldindan hisoblangan qiymatlarini saqlashni talab qiladi, lekin agar biz M prefiks funktsiyasi satrda olishi mumkin bo'lgan maksimal qiymatni oldindan bilsak, biz satrning faqat M+1 birinchi belgilarini saqlashimiz mumkin. prefiks funksiyasining qiymatlari soni. 1.3. Prefiks funktsiyasini qo’llanilishi Qatorda pastki qatorni qidiring. Knut-Morris-Pratt algoritmi Vazifa - bu prefiks funktsiyasining klassik qo'llanilishi. t matni va s satri berilgan bo‘lsa, biz t matnidagi s satrning barcha ko‘rinishlarining o‘rinlarini topib, ko‘rsatmoqchimiz. Qulaylik uchun n bilan s satr uzunligini va m bilan t matn uzunligini belgilaymiz. Biz s + \\# + t qatorini hosil qilamiz, bu erda \\# - na s, na t-da ko'rinmaydigan ajratuvchi. Keling, ushbu satr uchun prefiks funktsiyasini hisoblaylik. Endi prefiks funktsiyasi qiymatlarining ma'nosi haqida o'ylab ko'ring, birinchi n+1 yozuvlaridan tashqari (ular s qatoriga va ajratuvchiga tegishli). Ta'rifga ko'ra, π[i] qiymati 10$ $prefiksga to'g'ri keladigan i pozitsiyasida tugaydigan pastki qatorning eng uzun uzunligini ko'rsatadi. Ammo bizning holatlarimizda bu s bilan mos keladigan va i pozitsiyasida tugaydigan eng katta blokdan boshqa narsa emas. Bu uzunlik ajratuvchi tufayli n dan katta bo'lishi mumkin emas. Lekin agar π [ i]=n tengligiga erishilsa, demak, s satr shu holatda to'liq paydo bo'ladi, ya'ni u i pozitsiyada tugaydi. Shuni unutmangki, pozitsiyalar s + \\# + t qatorida indekslanadi. Shunday qilib, agar biron bir i pozitsiyada bizda p[i]=n bo'lsa, u holda t qatoridagi i−(n+1)−n+1=i−2n pozitsiyasida s qator paydo bo'ladi. Prefiks funktsiyasini hisoblash tavsifida aytib o'tilganidek, agar biz prefiks qiymatlari hech qachon ma'lum bir qiymatdan oshmasligini bilsak, unda biz butun satrni va butun funktsiyani saqlashimiz shart emas, faqat uning boshlanishi. Bizning holatimizda bu faqat s + \\ # satrini va uning uchun prefiks funktsiyasi qiymatlarini saqlashimiz kerakligini anglatadi. Biz t satrning bir vaqtning o'zida bitta belgini o'qiymiz va prefiks funktsiyasining joriy qiymatini hisoblashimiz mumkin. Shunday qilib, Knut-Morris-Pratt algoritmi muammoni O(n+m) vaqt va O(n) xotirada hal qiladi. Har bir prefiksning takrorlanish sonini hisoblash . Bu erda biz bir vaqtning o'zida ikkita muammoni muhokama qilamiz. Uzunligi n bo'lgan s qator berilgan. Muammoning birinchi variantida biz har bir s[0…i] prefiksining bir qatorda paydo bo'lish sonini hisoblamoqchimiz. Muammoning ikkinchi variantida yana bir qator t berilgan va biz har bir s[0…i] prefiksining t dagi ko‘rinishlar sonini hisoblamoqchimiz. Avval biz birinchi muammoni hal qilamiz. i pozitsiyasidagi π[i] prefiks funksiyasining qiymatini ko'rib chiqing. Ta'rifga ko'ra, bu i pozitsiyada s satrning π[i] uzunlikdagi prefiksi paydo bo'lishini va i pozitsiyasida tugashini anglatadi va bu ta'rifga mos keladigan uzunroq prefiks mavjud emas. Shu bilan birga, qisqaroq prefikslar bu holatda tugashi mumkin. Ko'rish qiyin emas, bizda prefiks funksiyasini o'zi hisoblashda javob bergan bir xil savol bor: i pozitsiyasida tugaydigan j uzunlikdagi prefiks berilgan bo'lsa, keyingi kichikroq prefiks <j nima? i pozitsiyasida tugaydigan qo‘shimcha ham. Shunday qilib, i pozitsiyasida uzunlikdagi π[i] prefiksi, uzunlikdagi π [π [i]−1] prefiksi, π [π [π [i]−1]−1] prefiksi 11$ $va boshqalar tugaydi, indeks nolga aylanmaguncha. Shunday qilib, javobni quyidagi tarzda hisoblashimiz mumkin. 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]++; Bu yerda prefiks funksiyasining har bir qiymati uchun avval uning p massivda necha marta sodir bo‘lishini hisoblaymiz, so‘ngra yakuniy javoblarni hisoblaymiz: agar i uzunlik prefiksi aynan ans[i] marta paydo bo‘lishini bilsak, bu raqamni qo‘shish kerak. prefiks ham bo'lgan uning eng uzun qo'shimchasining paydo bo'lish soniga. Oxirida har bir natijaga 1 qo'shishimiz kerak, chunki biz asl prefikslarni ham hisoblashimiz kerak. Endi ikkinchi muammoni ko'rib chiqaylik. Biz Knuth-Morris-Prattdan hiyla ishlatamiz: biz s + \\# + t qatorini yaratamiz va uning prefiks funktsiyasini hisoblaymiz. Birinchi vazifaning yagona farqi shundaki, bizni faqat t qatoriga tegishli prefiks qiymatlari qiziqtiradi, ya'ni i≥n+1 uchun p[i]. Ushbu qiymatlar bilan biz birinchi vazifadagi kabi bir xil hisob-kitoblarni bajarishimiz mumkin. Satrdagi turli pastki qatorlar soni Uzunligi n bo'lgan s qator berilgan. Biz unda paydo bo'ladigan turli pastki qatorlar sonini hisoblamoqchimiz. Biz bu muammoni takroriy hal qilamiz. Ya'ni, biz turli xil pastki qatorlarning joriy sonini bilib, oxiriga belgi qo'shish orqali ushbu sonni qanday qayta hisoblashni bilib olamiz. Shunday qilib, k s dagi turli pastki qatorlarning joriy soni bo'lsin va s ning oxiriga c belgisini qo'shamiz. Shubhasiz, c bilan tugaydigan ba'zi yangi pastki qatorlar paydo bo'ladi. Biz ilgari paydo bo'lmagan ushbu yangi pastki qatorlarni hisoblamoqchimiz. Biz t=s+c qatorini olamiz va uni teskari aylantiramiz. Endi vazifa boshqa joyda uchramaydigan qancha prefiks borligini hisoblashga aylantiriladi. Agar teskari 12$

satrning pmax prefiks funksiyasining maksimal qiymatini hisoblasak, u holda s da
paydo bo'ladigan eng uzun prefiks pmax long bo'ladi. Shubhasiz, unda kichikroq
uzunlikdagi barcha prefikslar ham paydo bo'ladi.
Shuning uchun biz c yangi belgi qo'shganda paydo bo'ladigan yangi pastki
qatorlar soni |s|+1−pmax. Shunday qilib, qo'shilgan har bir belgi uchun O(n) marta
yangi pastki qatorlar sonini hisoblashimiz mumkin, bu jami O(n2) vaqt
murakkabligini beradi. Shuni ta'kidlash kerakki, biz turli xil pastki qatorlar sonini
boshida belgilarni qo'shish yoki boshidan yoki oxiridan belgilarni o'chirish orqali
ham hisoblashimiz mumkin.
Qatorni siqish
Uzunligi n bo'lgan s qator berilgan. Biz satrning eng qisqa "siqilgan" ko'rinishini
topmoqchimiz, ya'ni eng kichik uzunlikdagi t qatorni topmoqchimiz, shunda s t
ning bir yoki bir nechta nusxalarining birikmasi sifatida ifodalanishi mumkin.
Biz faqat t uzunligini topishimiz kerakligi aniq. Uzunlikni bilgan holda,
muammoning javobi bu uzunlikdagi s prefiksi bo'ladi.
s uchun prefiks funksiyasini hisoblaylik. Uning oxirgi qiymatidan foydalanib,
k=n−π[n−1] qiymatini aniqlaymiz. Biz shuni ko'rsatamizki, agar k n ni bo'lsa, u
holda k javob bo'ladi, aks holda samarali siqish mavjud emas va javob n bo'ladi.
n soni k ga bo‘linsin. Keyin ipni k uzunlikdagi bloklarga bo'lish mumkin. Prefiks
funktsiyasining ta'rifiga ko'ra, n-k uzunlikdagi prefiks uning qo'shimchasi bilan
teng bo'ladi. Ammo bu oxirgi blok oldingi blokga teng ekanligini anglatadi. Va
oldingi blok oldingi blokga teng bo'lishi kerak. Va hokazo. Natijada, barcha
bloklar teng ekanligi ma'lum bo'ldi, shuning uchun biz s qatorni k uzunlikka siqib
qo'yishimiz mumkin.
Albatta, biz hali ham bu aslida eng maqbul ekanligini ko'rsatishimiz kerak.
Haqiqatan ham, agar k dan kichikroq siqilish bo'lsa, oxiridagi prefiks funktsiyasi n-
k dan kattaroq bo'lar edi. Shuning uchun k haqiqatan ham javobdir.
Endi n ni k ga bo'linmaydi deb faraz qilaylik. Bu javobning uzunligi n ekanligini
bildirishini ko'rsatamiz. Biz buni qarama-qarshilik bilan isbotlaymiz. Agar javob
bor deb faraz qilsak va siqilish p uzunligiga ega (π n ni ajratadi). Keyin prefiks
13

$funktsiyasining oxirgi qiymati n- π dan katta bo'lishi kerak, ya'ni qo'shimcha birinchi blokni qisman qoplaydi. Endi satrning ikkinchi blokini ko'rib chiqing. Prefiks qo'shimcha bilan teng bo'lgani uchun va prefiks ham, qo'shimcha ham bu blokni qamrab oladi va ularning bir-biriga nisbatan siljishi k blok uzunligini p ajratmaydi (aks holda k n ni ajratadi), u holda blokning barcha belgilari bir xil bo'lsin. Ammo keyin satr qayta-qayta takrorlanadigan faqat bitta belgidan iborat bo'ladi, shuning uchun biz uni 1 o'lchamdagi qatorga siqib qo'yishimiz mumkin, bu k=1 beradi va k n ni ajratadi. Qarama-qarshilik. 7-rasm. Prefiks funktsiyasiga ko'ra avtomatni qurish Keling, ajratuvchi orqali ikkita satrni birlashtirishga qaytaylik, ya'ni s va t satrlari uchun s + \\# + t qatori uchun prefiks funktsiyasini hisoblaymiz. Shubhasiz, \\ # ajratuvchi bo'lgani uchun, prefiks funktsiyasining qiymati hech qachon |s| dan oshmaydi. Bundan kelib chiqadiki, faqat s + \\# satrini va uning uchun prefiks funktsiyasi qiymatlarini saqlash kifoya va biz barcha keyingi belgilar uchun prefiks funktsiyasini tezda hisoblashimiz mumkin: \underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ \\#}\_{\text{saqlash kerak}} ~ \ underbrace{t_0 ~ t_1 ~ \dots ~ t_{m-1}} \_{\matn{saqlash shart emas}} Darhaqiqat, bunday vaziyatda keyingi c ∈ t belgisini va oldingi pozitsiyaning prefiks funktsiyasining qiymatini bilish t satrining oldingi belgilaridan va qiymatdan foydalanmasdan, prefiks funktsiyasining keyingi qiymatini hisoblash uchun etarli ma'lumotdir. ulardagi prefiks funktsiyasi. Boshqacha qilib aytganda, biz avtomat (cheklangan holat mashinasi) qurishimiz mumkin: undagi holat prefiks funktsiyasining joriy qiymati bo'lib, bir holatdan ikkinchi holatga o'tish keyingi belgi orqali amalga oshiriladi. 14$ $Shunday qilib, t qatoriga ega bo'lmasdan ham, biz o'tish jadvalini hisoblash algoritmidan foydalangan holda bunday o'tish jadvalini (oldp,c)→newp qurishimiz mumkin: 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; } } } Biroq bu shaklda algoritm alifboning kichik harflari uchun O(N 2 26) vaqtida ishlaydi. E'tibor bering, biz dinamik dasturlashni qo'llashimiz va jadvalning allaqachon hisoblangan qismlaridan foydalanishimiz mumkin. Biz j qiymatidan π[j−1] qiymatiga o‘tsak, biz aslida (j,c) o‘tish (π[j−1],c) kabi o‘tish holatiga olib kelishini tushunamiz va bu javob allaqachon aniq hisoblangan. 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++) { 15$ $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]); } } } Natijada biz avtomatni O(n 2 26) vaqtida quramiz. Bunday avtomat qachon foydali? Boshlash uchun esda tutingki, biz s + \\# + t qatori va uning qiymatlari uchun prefiks funktsiyasidan asosan bitta maqsadda foydalanamiz: t satrida s satrining barcha takrorlanishini toping. Shuning uchun bu avtomatning eng aniq foydasi s + \\ # + t qatori uchun prefiks funktsiyasini hisoblashning tezlashishi hisoblanadi. s + \\# uchun avtomatni yaratish orqali biz endi s satrini yoki undagi prefiks funksiyasining qiymatlarini saqlashimiz shart emas. Barcha o'tishlar allaqachon jadvalda hisoblangan. Ammo ikkinchi, kamroq ravshan dastur bor. Avtomatdan t qatori ba'zi qoidalar yordamida tuzilgan ulkan satr bo'lganda foydalanishimiz mumkin. Bu, masalan, kulrang satrlar yoki kirishdan bir nechta qisqa satrlarning rekursiv birikmasidan hosil bo'lgan satr bo'lishi mumkin. To'liqlik uchun biz shunday masalani hal qilamiz: k≤10 5 son va ≤10 5 uzunlikdagi s qator berilgan. Biz k-Gray qatorda s ning takrorlanish sonini hisoblashimiz kerak. Eslatib o'tamiz, Greyning satrlari quyidagi tarzda aniqlanadi: 8-rasm . Bunday hollarda, astronomik uzunligi tufayli t qatorini qurish ham imkonsiz bo'ladi. k -kulrang qator uzunligi 2 k −1 belgidan iborat. Biroq, satr oxiridagi prefiks 16$

funktsiyasining qiymatini faqat boshida prefiks funktsiyasi qiymatini bilish orqali
samarali hisoblashimiz mumkin.
Avtomatning o'zidan tashqari, biz G[i][j] qiymatlarini ham hisoblaymiz - j
holatidan boshlanadigan gi satrini qayta ishlashdan keyin avtomatning qiymati. Va
qo'shimcha ravishda biz K[i][j] qiymatlarini hisoblaymiz - j holatidan boshlab gi ni
qayta ishlashdan oldin gi dagi s ning paydo bo'lish sonini. Aslida K[i][j] - prefiks
funksiyasi necha marta |s| qiymatini olgan operatsiyalarni bajarayotganda.
Muammoning javobi u holda K[k][0] bo'ladi.
Ushbu qiymatlarni qanday hisoblashimiz mumkin? Birinchidan, asosiy qiymatlar
G[0][j]=j va K[0][j]=0. Va barcha keyingi qiymatlar oldingi qiymatlardan va
avtomat yordamida hisoblanishi mumkin. Ba'zi i uchun qiymatni hisoblash uchun
gi qatori gi-1, alifboning i belgisi va gi-1 dan iborat ekanligini eslaymiz. Shunday
qilib, avtomat quyidagi holatga o'tadi:
9-rasm.
K[i][j] qiymatlarini ham oson sanash mumkin.
K [ i ][ j ]= K [ i − 1 ][ j ]+( mid ==| s |)+ K [ i − 1 ][ mid ]
Shunday qilib, biz kulrang satrlar muammosini va shunga o'xshash juda ko'p
boshqa shunga o'xshash muammolarni hal qilishimiz mumkin. Masalan, xuddi shu
usul quyidagi muammoni ham hal qiladi: bizga s qatori va ba'zi naqshlar ti
berilgan, ularning har biri quyidagicha ko'rsatilgan: bu oddiy belgilar qatori va
oldingi satrlarning ba'zi rekursiv qo'shilishi bo'lishi mumkin. tcntk shaklining, ya'ni
bu joyga biz tk cnt marta qatorini kiritishimiz kerak. Bunday naqshlarga misol:
17

10-rasm.
Rekursiv almashtirishlar satrini tezlashtiradi, shunda ularning uzunligi 100 100
ga
yetishi mumkin.
Har bir satrda s qatori necha marta paydo bo'lishini topishimiz kerak.
Prefiks funktsiyasining avtomatini qurish orqali muammoni xuddi shunday hal
qilish mumkin, keyin esa oldingi natijalardan foydalanib, har bir naqsh uchun
o'tishlarni hisoblaymiz.
I I -BOB. KNUT-MORISS-PRATT ALGORITMI
2.1. Knut-Morris-Pratt algoritmi
Knuth-Morris-Pratt (KMP) algoritmi chiziqli vaqt ichida satrdan prefiks
funksiyasini topishga imkon beradi va sodda algoritmdan oshmaydigan darajada
ixcham amalga oshirishga ega.

1-rasm. Donald Knut (1938 yilda tug'ilgan), Jeyms Morris (1941 yilda
tug'ilgan), Von Pratt (1944 yilda tug'ilgan).
Knut – Morris – Pratt satrlarni qidirish algoritmi (yoki KMP algoritmi) "so'z"
ning paydo bo'lishini qidiradi V asosiy "matn satri" ichida S nomuvofiqlik yuzaga
kelganda, so'zning o'zi keyingi o'yin qayerda boshlanishi mumkinligini aniqlash
uchun etarli ma'lumotni o'zida mujassam etganligi va shu bilan ilgari mos
keladigan belgilarni qayta tekshirishni chetlab o'tganligini kuzatish orqali.
Algoritm tomonidan homilador bo'lgan Jeyms H. Morris tomonidan mustaqil
ravishda kashf etilgan Donald Knuth "bir necha hafta o'tgach" dan avtomatlar
nazariyasi.[1][2]Morris va Vaughan Pratt 1970 yilda texnik hisobotni nashr etdi.
[3]Uchalasi ham 1977 yilda birgalikda algoritmni nashr etishdi.[1] Mustaqil
18

ravishda, 1969 yilda, Matiyasevich[4][5] Ikki o'lchovli Turing mashinasi
tomonidan kodlangan shunga o'xshash algoritmni, ikkilik alifbo bo'yicha satr
naqshiga mos keladigan tanib olish muammosini o'rganayotganda topdi. Bu
satrlarni moslashtirish uchun birinchi chiziqli vaqt algoritmi edi.[6]
Bir qatorga mos keladigan algoritm boshlang'ich indeksini topishni xohlaydi m
ipda S [] bu qidiruv so'ziga mos keladi V [].
"Deb nomlanuvchi eng to'g'ri algoritmQo'pol kuch"yoki" sodda "algoritmi, har bir
indeksda so'z mosligini izlashdir m, ya'ni izlanayotgan satrdagi pozitsiyaga mos
keladigan pozitsiya S [m]. Har bir pozitsiyada m algoritm birinchi navbatda
qidirilayotgan so'zdagi birinchi belgining tengligini tekshiradi, ya'ni. S [m] =? V
[0]. Agar moslik topilsa, algoritm qidirilayotgan so'zning boshqa belgilarini
pozitsiya indeksining ketma-ket qiymatlarini tekshirish orqali tekshiradi, men.
Algoritm belgini oladi V [i] qidirilayotgan so'zda va ifodaning tengligini tekshiradi
S [m + i] =? V [i]. Agar barcha ketma-ket belgilar mos keladigan bo'lsa V holatida
m, keyin qidirish satrida mos keladigan joy topiladi. Agar indeks bo'lsa m
mag'lubiyatning oxiriga etib boradigan bo'lsa, unda mos kelmaydi, bu holda
qidiruv "muvaffaqiyatsiz" deb aytiladi.
Odatda, sinov tekshiruvi sinov o'yinini tezda rad etadi. Agar satrlar bir tekis
taqsimlangan tasodifiy harflar bo'lsa, unda belgilar mos kelish ehtimoli 26 dan 1 ga
teng. Ko'p hollarda, sinov tekshiruvi o'yinni dastlabki harfda rad etadi. Dastlabki
ikkita harf mos kelish ehtimoli 26 dan 1 ga teng2 (676 dan 1). Agar belgilar
tasodifiy bo'lsa, unda qidirish satrining kutilayotgan murakkabligi S [] uzunlik n
buyurtmasi bo'yicha n taqqoslashlar yoki O(n). Kutilayotgan ko'rsatkich juda
yaxshi. Agar S [] 1 million belgidan iborat va V [] 1000 belgidan iborat, keyin
satrlarni qidirish taxminan 1,04 million belgini taqqoslagandan so'ng yakunlanishi
kerak. Ushbu kutilgan ishlash kafolatlanmagan. Agar satrlar tasodifiy bo'lmasa,
unda sinovni tekshiring m ko'pgina belgilarni taqqoslashi mumkin. Eng yomon
holat, agar ikkita satr oxirgi harfdan boshqasiga to'g'ri keladigan bo'lsa. Tasmani
tasavvur qiling S [] barchasi 1 million belgidan iborat Ava bu so'z V [] 999 ni
tashkil qiladi A finalda tugaydigan belgilar B belgi. Oddiy satrlarni moslashtirish
19

algoritmi endi o'yinni rad etishdan va sinov holatiga o'tishdan oldin har bir sinov
holatida 1000 ta belgini tekshiradi. Oddiy satrlarni qidirish misoli endi 1000 ta
belgini taqqoslash uchun 1 million pozitsiyani 1 milliard belgini taqqoslash uchun
kerak bo'ladi. Agar uzunligi V [] bu k, unda eng yomon ko'rsatkich O(k ⋅ n).
KMP algoritmi to'g'ridan-to'g'ri algoritmga qaraganda yomonroq ko'rsatkichlarga
ega. KMP jadvalni oldindan hisoblash uchun oz vaqt sarflaydi (hajmi tartibida V
[], O(k)), keyin esa ushbu jadval yordamida satrni samarali qidirishni amalga
oshiradi O(n).
Farqi shundaki, KMP to'g'ridan-to'g'ri algoritmda mavjud bo'lmagan oldingi o'yin
ma'lumotlaridan foydalanadi. Yuqoridagi misolda, KMP 1000-chi belgida sinov
o'yinida muvaffaqiyatsizlikka uchraganini ko'rganda (men = 999), chunki S [m +
999] ≠ V [999], u ortadi m 1 ga, ammo yangi pozitsiyadagi birinchi 998 ta belgi
allaqachon mos kelishini biladi. KMP 999 ga to'g'ri keldi A 1000-belgidagi
nomuvofiqlikni aniqlashdan oldin belgilar (999-pozitsiya). Sinov uchrashuvi
pozitsiyasini oldinga siljitish m birinchisi birinchisini tashlaydi A, shuning uchun
KMP 998 ta ekanligini biladi A mos keladigan belgilar V [] va ularni qayta
sinovdan o'tkazmaydi; ya'ni KMP to'plamlari men 998 gacha. KMP o'z bilimlarini
oldindan hisoblangan jadvalda va ikkita holat o'zgaruvchilarida saqlaydi. KMP
nomuvofiqlikni aniqlaganda, jadval KMP qancha ko'payishini aniqlaydi
(o'zgaruvchan m) va u sinovni qayta boshlaydigan joy (o'zgaruvchan) men).
KMP algoritmi
Qidiruv algoritmiga misol
Algoritm tafsilotlarini ko'rsatish uchun algoritmning (nisbatan sun'iy) ishlashini
ko'rib chiqing, bu erda V = "ABCDABD" va S = "ABC ABCDAB
ABCDABCDABDE". Istalgan vaqtda algoritm ikkita butun son bilan aniqlangan
holatda bo'ladi:
m, ichidagi pozitsiyani bildiradi S istiqbolli o'yin qaerda V boshlanadi,
men, hozirda ko'rib chiqilayotgan belgi indeksini bildiradi V.
Har bir bosqichda algoritm taqqoslanadi S [m + i] bilan V [i] va o'sish men agar
ular teng bo'lsa. Bu, masalan, yugurish boshida tasvirlangan
20

1 2 m: 01234567890123456789012S: ABCABCDAB
ABCDABCDABDEV: ABCD.ABDmen: 0123456
Algoritm ning ketma-ket belgilarini taqqoslaydi V ning "parallel" belgilariga S,
o'sish orqali biridan ikkinchisiga o'tish men agar ular mos keladigan bo'lsa. Biroq,
to'rtinchi bosqichda S [3] = " mos kelmaydi V [3] = 'D'. Qayta qidirishni
boshlashdan ko'ra S [1], biz yo'q deb ta'kidlaymiz "A" 1 va 2 pozitsiyalar orasida
sodir bo'ladi S; shuning uchun barcha ushbu belgilarni oldindan tekshirib (va
ularning tegishli belgilarga mos kelishini bilib) V), o'yin boshlanishini topish
imkoniyati yo'q. Shuning uchun algoritm belgilanadi m = 3 va i = 0.
1 2 m: 01234567890123456789012S: ABCABCDAB
ABCDABCDABDEV: ABCDABDmen: 0123456
Ushbu o'yin dastlabki belgida muvaffaqiyatsiz tugadi, shuning uchun algoritm
o'rnatiladi m = 4 va i = 0
1 2 m: 01234567890123456789012S: ABC
ABCDABABCDABCDABDEV: ABCDABD.men: 0123456
Bu yerda, men deyarli to'liq o'yin orqali o'sish "ABCDAB" qadar i = 6
nomuvofiqlikni berish V [6] va S [10]. Biroq, hozirgi qisman o'yin tugashidan
biroz oldin, bu pastki chiziq bor edi "AB" bu yangi o'yinning boshlanishi bo'lishi
mumkin, shuning uchun algoritm buni hisobga olishi kerak. Ushbu belgilar joriy
pozitsiyadan oldin ikkita belgiga to'g'ri kelganligi sababli, bu belgilarni qayta
tekshirishga hojat yo'q; algoritm to'plamlari m = 8 (dastlabki prefiksning
boshlanishi) va i = 2 (dastlabki ikkita belgi mos kelishini bildiradi) va
moslashtirishni davom ettiradi. Shunday qilib, algoritm nafaqat ilgari mos
keladigan belgilarni chiqarib tashlaydi S (the "AB"), shuningdek, ilgari mos
keladigan belgilar V (prefiks "AB").
1 2 m: 01234567890123456789012S: ABC
ABCDABABCDABCDABDEV: ABCDABDmen: 0123456
Ushbu yangi pozitsiyada qidirish darhol muvaffaqiyatsiz tugadi, chunki V [2] (a
"C") mos kelmaydi S [10] (a ' '). Birinchi sinovda bo'lgani kabi, mos kelmaslik
21

algoritmning boshiga qaytishiga olib keladi V va mos kelmagan belgi holatidan
qidirishni boshlaydi S: m = 10, qayta o'rnatish i = 0.
1 2 m: 01234567890123456789012S: ABC
ABCDABABCDABCDABDEV: ABCDABDmen: 0123456
Uchrashuv m = 10 darhol ishlamay qoladi, shuning uchun algoritm keyingi
harakatlarni bajaradi m = 11 va i = 0.
1 2 m: 01234567890123456789012S: ABC ABCDAB
ABCDABCDABDEV: ABCDABD.men: 0123456
Algoritm yana bir bor mos keladi "ABCDAB", lekin keyingi belgi, "C", yakuniy
belgiga mos kelmaydi "D" so'zning V. Oldingi kabi fikr yuritib, algoritm
o'rnatiladi m = 15, ikki belgidan iborat qatordan boshlash uchun "AB" o'rnatilgan
holatga qadar olib boradi i = 2va amaldagi holatidan mos kelishni davom eting.
1 2 m: 01234567890123456789012S: ABC ABCDAB
ABCDABCDABDEV: ABCDABDmen: 0123456
Bu safar o'yin tugallandi va o'yinning birinchi belgisi S [15].
Qidiruv algoritmi uchun psevdokod tavsifi
Yuqoridagi misol algoritmning barcha elementlarini o'z ichiga oladi. Hozircha biz
"qisman o'yin" jadvali mavjudligini taxmin qilamiz Ttasvirlangan quyida, bu
hozirgi o'yin nomuvofiqlikda tugagan taqdirda yangi o'yin boshlanishini qaerdan
qidirishimiz kerakligini ko'rsatadi. Yozuvlari T Bizda o'yin boshlanadigan bo'lsa,
shunday qilib qurilgan S [m] taqqoslaganda muvaffaqiyatsiz bo'ladi S [m + i] ga V
[i], keyin keyingi mumkin bo'lgan o'yin indeksdan boshlanadi m + i - T [i] yilda S
(anavi, T [i] - mos kelmaslikdan keyin qilishimiz kerak bo'lgan "orqaga qaytish"
miqdori). Buning ikkita ta'siri bor: birinchi, T [0] = -1, bu shuni ko'rsatadiki V [0]
nomuvofiqlik, biz orqaga qaytishimiz mumkin emas va shunchaki keyingi belgini
tekshirishimiz kerak; ikkinchidan, garchi keyingi mumkin bo'lgan o'yin bo'ladi
boshlash indeksda m + i - T [i], yuqoridagi misolda bo'lgani kabi, biz aslida
birortasini tekshirmasligimiz kerak T [i] bundan keyin belgilar, shuning uchun biz
qidirishni davom ettiramiz V [T [i]]. Quyida namuna keltirilgan psevdokod KMP
qidiruv algoritmini amalga oshirish.
22

algoritm kmp_search: kiritish: belgilar qatori, S (qidirilayotgan matn) belgilar
qatori, W (qidirilayotgan so'z) chiqish: P butun sonlar qatori, P (S-da W topilgan
pozitsiyalar) butun son, nP (pozitsiyalar soni) o'zgaruvchilarni aniqlang: tamsayı, j
← 0 (joriy belgining S-dagi o'rni) butun son, k ← 0 (joriy belgining Wdagi holati)
butun sonli qator, T (boshqa joyda hisoblangan jadval) ruxsat bering nP ← 0 esa j
qil agar V [k] = S [j] keyin ruxsat bering j ← j + 1 ruxsat bering k ← k
+ 1 agar k = uzunlik (V) keyin (hodisa aniqlandi, agar birinchi marta
paydo bo'lishi kerak bo'lsa, m ← j - k bu erga qaytarilishi mumkin) ruxsat bering P
[nP] ← j - k, nP ← nP + 1 ruxsat bering k ← T [k] (T [uzunlik (W)] -1 bo'lishi
mumkin emas) boshqa ruxsat bering k ← T [k] agar k <0 keyin
ruxsat bering j ← j + 1 ruxsat bering k ← k + 1
Qidiruv algoritmining samaradorligi
Jadvalning avvalgi mavjudligini taxmin qilish T, Knuth-Morris-Pratt
algoritmining qidiruv qismi mavjud murakkablik O(n), qayerda n ning uzunligi S
va O bu katta-O notation. Funktsiyaga kirish va chiqishda yuzaga keladigan qattiq
xarajatlar bundan mustasno, barcha hisoblashlar esa pastadir Ushbu tsiklning
takrorlanish sonini chegaralash uchun; buni kuzating T o'yin boshlangan bo'lsa,
shunday qilib qurilgan S [m] taqqoslash paytida muvaffaqiyatsizlikka uchraydi S
[m + i] ga V [i], keyin keyingi mumkin bo'lgan o'yin boshlanishi kerak S [m + (i -
T [i])]. Xususan, keyingi mumkin bo'lgan o'yin nisbatan yuqori indeksda bo'lishi
kerak m, Shuning uchun; ... uchun; ... natijasida T [i] .
Bu haqiqat shuni anglatadiki, loop eng ko'p 2 bajarishi mumkinn marta, chunki
har bir takrorlashda u tsikldagi ikkita filialdan birini bajaradi. Birinchi filial doimo
ko'payib boradi men va o'zgarmaydi m, shuning uchun indeks m + i ning hozirda
tekshirilayotgan xarakteridan S oshirildi. Ikkinchi filial qo'shiladi i - T [i] ga m, va
biz ko'rganimizdek, bu har doim ijobiy raqam. Shunday qilib joylashuv m joriy
potentsial uchrashuvi boshi oshirildi. Shu bilan birga, ikkinchi filial ketadi m + i
o'zgarmagan, chunki m oladi i - T [i] unga qo'shildi va darhol keyin T [i] ning
yangi qiymati sifatida tayinlanadi men, demak new_m + new_i = old_m + old_i -
T [old_i] + T [old_i] = old_m + old_i. Endi, agar tugatish tugaydi m + i = n;
23

shuning uchun tsiklning har bir tarmog'iga maksimal darajada erishish mumkin n
marta, chunki ular mos ravishda ikkalasi ham ko'payadi m + i yoki mva m ≤ m + i:
agar m = n, keyin albatta m + i ≥ n, shuning uchun u eng ko'p birlik o'sishiga
ko'paygani uchun bizda bo'lishi kerak edi m + i = n o'tmishda bir nuqtada, va
shuning uchun biz har qanday yo'l bilan amalga oshiriladi.
Shunday qilib, tsikl maksimal 2 ni bajaradin marta, qidiruv algoritmining vaqt
murakkabligi ekanligini ko'rsatib beradi O(n).
Ish vaqti haqida o'ylashning yana bir usuli bu erda: biz mos kelishni boshlaymiz
deylik V va S holatida men va p. Agar V substring sifatida mavjud S p da, keyin V
[0..m] = S [p..p + m].Muvaffaqiyatli bo'lgandan keyin, ya'ni so'z va matn joylarga
mos keladi (W [i] = S [p + i]), biz ko'paytiramiz men tomonidan 1. Qobiliyatsiz
tugashi bilan, ya'ni so'z va matn joylarga mos kelmaydi (W [i] ≠ S [p + i]),
ko'rsatgich so'zi ma'lum bir miqdordagi orqaga qaytarilganda, matn ko'rsatkichi
harakatsiz saqlanadi (i = T [i], qayerda T va biz mos kelishga harakat qilamiz V [T
[i]] bilan S [p + i]Orqaga qaytarishning maksimal soni men bilan chegaralangan
men, ya'ni har qanday nosozlik uchun biz faqatgina muvaffaqiyatsizlikka qadar
borganimizcha orqaga qaytishimiz mumkin, shunda ish vaqti 2 ga tengn.
"Qisman o'yin" jadvali ("muvaffaqiyatsizlik funktsiyasi" deb ham nomlanadi)
Jadvalning maqsadi algoritmning har qanday belgiga mos kelmasligiga imkon
berishdir S bir martadan ko'proq. Bunga imkon beradigan chiziqli qidiruvning
mohiyati to'g'risida asosiy kuzatuv shundan iboratki, asosiy satrning ba'zi
segmentlarini dastlabki segment naqsh bo'yicha, biz aniq bilamizki, hozirgi holatga
qadar davom etishi mumkin bo'lgan yangi potentsial o'yin, hozirgi holatdan oldin
boshlanishi mumkin. Boshqacha qilib aytganda, biz naqshning o'zini "oldindan
qidiramiz" va buning uchun potentsial o'yinlarni sarf qilmasdan, maksimal umidsiz
belgilarni chetlab o'tadigan barcha mumkin bo'lgan pasayish pozitsiyalarining
ro'yxatini tuzamiz.
Biz har bir pozitsiya uchun yuqoriga qarab qarashni xohlaymiz V, ning eng uzun
boshlang'ich segmentining uzunligi V boshlanadigan to'liq segmentdan tashqari,
ushbu holatga qadar (lekin shu jumladan emas) V [0] faqat mos kelmadi; bu
24

keyingi o'yinni topishda orqaga qaytishimiz kerak. Shuning uchun T [i] mumkin
bo'lgan eng uzunning uzunligi to'g'ri ning boshlang'ich segmenti V bu ham
tugaydigan substring segmentidir V [i - 1]. Biz bo'sh satrning uzunligi 0 ga teng
bo'lgan konventsiyadan foydalanamiz, chunki naqshning boshida mos kelmaslik
alohida holat (orqaga qaytish imkoniyati yo'q). T [0] = -1, muhokama qilinganidek
quyida.
Jadval yaratish algoritmining ishchi misoli
Biz misolini ko'rib chiqamiz V = "ABCDABD" birinchi. Ko'rinib turibdiki, bu
asosiy qidirish bilan bir xil naqshga amal qiladi va shunga o'xshash sabablarga
ko'ra samarali bo'ladi. Biz o'rnatdik T [0] = -1. Topmoq T [1], biz kashf qilishimiz
kerak to'g'ri qo'shimchalar ning "A" bu shuningdek naqshning prefiksi V. Ammo
tegishli qo'shimchalar mavjud emas "A", shuning uchun biz o'rnatdik T [1] = 0.
Topmoq T [2], biz substringni ko'rayapmiz V [0] - V [1] ("AB") tegishli
qo`shimchasiga ega "B". Ammo "B" naqshning prefiksi emas V. Shuning uchun,
biz o'rnatdik T [2] = 0.
Davom etamiz T [3], avval biz 1 uzunlikdagi to'g'ri qo'shimchani tekshiramiz va
oldingi holatda bo'lgani kabi u ishlamay qoladi. Yana uzunroq qo'shimchalarni
tekshirishimiz kerakmi? Yo'q, endi tekshirish uchun yorliq borligini ta'kidlaymiz
barchasi qo'shimchalar: biz kashf etganimizni aytaylik to'g'ri qo'shimchalar bu
to'g'ri prefiks (Ipning to'g'ri prefiksi satrning o'ziga teng emas) va bilan tugaydi V
[2] uzunligi 2 bilan (maksimal mumkin); unda uning birinchi belgisi ham tegishli
prefiks hisoblanadi V, shuning uchun to'g'ri prefiksning o'zi va u tugaydi V [1], biz
allaqachon aniqlaganimiz kabi sodir bo'lmadi T [2] = 0 va emas T [2] = 1. Shunday
qilib, har bir bosqichda yorliq qoidasi shundan iboratki, agar avvalgi bosqichda m
o'lchamdagi amaldagi qo'shimchalar topilgan bo'lsa, ya'ni m + 1 berilgan
kattalikdagi qo'shimchalarni tekshirish kerak. T [x] = m) va m + 2, m + 3 va
boshqalarni tekshirishdan bezovtalanmaslik kerak.
Shuning uchun, biz hatto uzunligi 2 bo'lgan pastki chiziqlar bilan o'zimizni
tashvishlantirmasligimiz kerak, va oldingi holatda bo'lgani kabi uzunligi 1 bo'lgan
yagona ishlamay qoladi, shuning uchun T [3] = 0.
25

Biz keyingi qismga o'tamiz V [4], "A". Xuddi shu mantiq shuni ko'rsatadiki, biz
ko'rib chiqishimiz kerak bo'lgan eng uzun substring uzunligi 1 ga teng va avvalgi
holatda bo'lgani kabi, u ishlamay qolmoqda, chunki "D" bu prefiks emas V. Lekin
sozlash o'rniga T [4] = 0, buni ta'kidlab, yaxshiroq qilishimiz mumkin V [4] = V
[0], shuningdek, bu qarash T [4] tegishli narsani nazarda tutadi S belgi, S [m + 4],
mos kelmas edi va shuning uchun S [m + 4] ≠ 'A'. Shunday qilib qidirishni qayta
boshlashning foydasi yo'q S [m + 4]; biz oldinda 1 pozitsiyadan boshlashimiz
kerak. Bu shuni anglatadiki, biz naqshni almashtirishimiz mumkin V o'yin uzunligi
va bitta belgi bo'yicha, shuning uchun T [4] = -1.
Endi keyingi belgini hisobga olgan holda, V [5], bu "B": garchi tekshiruv orqali
eng uzun substring ko'rinadi "A", biz hali ham o'rnatamiz T [5] = 0. Fikrlash nima
uchun o'xshash T [4] = -1. V [5] o'zi boshlangan prefiks o'yinini kengaytiradi V
[4], va biz mos keladigan belgini S, S [m + 5] ≠ 'B'. Oldindan orqaga qaytish V [5]
ma'nosiz, ammo S [m + 5] balki "A", demak T [5] = 0.
Va nihoyat, davom etayotgan segmentdagi keyingi belgi boshlanishini ko'ramiz V
[4] = 'A' bo'lardi "B"va, albatta, bu ham V [5]. Bundan tashqari, yuqoridagi dalillar
shuni ko'rsatadiki, biz ilgari qarashimiz shart emas V [4] uchun segmentni topish V
[6], shuning uchun bu shunday, va biz olamiz T [6] = 2.
Shuning uchun biz quyidagi jadvalni tuzamiz:
men 0 1 2 3 4 5 6 7
V [i] A B C D. A B D.
T [i] -1 0 0 0 -1 0 2 0
Yana bir misol:
men 0 1 2 3 4 5 6 7 8 9
V [i] A B A C A B A B C
T [i] -1 0 -1 1 -1 0 -1 3 2 0
Yana bir misol (oldingi misoldan biroz o'zgardi):
men 0 1 2 3 4 5 6 7 8 9
26

V [i] A B A C A B A B A
T [i] -1 0 -1 1 -1 0 -1 3 -1 3
Yana bir murakkab misol:
men 00 01 02 03 04 05 06 07 08 09 10 11
12 13 14 15 16 17 18 19 20 21 22 23
24
V [i] P A R T Men C Men P A T E
Men N P A R A C H U T E
T [i] -1 0 0 0 0 0 0 -1 0 2 0 0 0
0 0 -1 0 0 3 0 0 0 0 0 0
Jadval yaratish algoritmi uchun psevdokod tavsifi
Yuqoridagi misol stolni minimal shovqin bilan yig'ishning umumiy texnikasini
tasvirlaydi. Ushbu tamoyil umumiy izlanishdir: ishlarning aksariyati hozirgi
mavqega erishish uchun allaqachon qilingan, shuning uchun uni tark etish uchun
juda oz narsa qilish kerak. Faqatgina kichik murakkablik shundaki, mag'lubiyat
oxirida to'g'ri bo'lgan mantiq noto'g'ri boshida noto'g'ri chiziqlarni beradi. Bu ba'zi
bir boshlang'ich kodlarini talab qiladi.
algoritm kmp_table: kiritish: W belgilar qatori (tahlil qilinadigan so'z) chiqish: T
butun qator, T (to'ldiriladigan jadval) o'zgaruvchilarni aniqlang: tamsayı, pos ← 1
(biz Tda hisoblayotgan joriy holat) tamsayı, cnd ← 0 (joriy nomzod substringining
keyingi belgisidagi Wdagi nolga asoslangan indeks) ruxsat bering T [0] ← -1 esa
pos qil agar W [pos] = W [cnd] keyin ruxsat bering T [pos] ← T [cnd]
boshqa ruxsat bering T [pos] ← cnd ruxsat bering cnd ← T [cnd] (ishlashni
oshirish uchun) esa cnd ≥ 0 va W [pos] ≠ W [cnd] qil ruxsat bering cnd
← T [cnd] ruxsat bering pos ← pos + 1, cnd ← cnd + 1 ruxsat bering T [pos] ←
cnd (faqat barcha so'zlar qidirilganda kerak bo'ladi)
Jadval yaratish algoritmining samaradorligi
Jadval algoritmining vaqt (va shu bilan bo'shliq) murakkabligi Ok), qayerda k ning
uzunligi V.
27

Tashqi tsikl: pos boshlang'ich qiymati 1 ga, tsikl sharti pos va pos tsiklning har bir
takrorlanishida 1 ga ko'paytiriladi. Shunday qilib, ko'chadan o'tadi k - 1 takrorlash.
Ichki halqa: cnd uchun boshlangan 0 va har bir tashqi tsiklning takrorlanishida
maksimal 1 ga ko'payadi. T [cnd] har doim kamroq cnd, shuning uchun cnd har bir
ichki tsiklning takrorlanishida kamida 1 ga kamayadi; ichki pastadir holati cnd ≥ 0.
Bu shuni anglatadiki, ichki tsikl jami eng ko'p marta bajarishi mumkin, chunki
tashqi tsikl bajarilgan - har bir pasayish cnd ichki tsikldagi 1 ga tashqi tsikldagi 1
ga mos keladigan o'sish kerak. Tashqi ko'chadan beri k - 1 takrorlash, ichki tsikl
ko'pi bilan qabul qilishi mumkin k - 1 jami takrorlash.
Birlashtirilgan holda tashqi va ichki halqalar maksimal darajada olinadi
{ displaystyle 2k-2} takrorlash. Bu mos keladi Ok) yordamida vaqt murakkabligi
Big O notation.
KMP algoritmining samaradorligi
Algoritmning ikkita qismi mos ravishda murakkabliklarga ega bo'lgani uchun Ok)
va O (n), umumiy algoritmning murakkabligi O (n + k).
Qanchalik takrorlanadigan naqshlar bo'lishidan qat'i nazar, bu murakkabliklar bir
xil V yoki S.
Variantlar
A haqiqiy vaqt KMP versiyasi alfavitdagi har bir belgi uchun alohida funktsiya
jadvali yordamida amalga oshirilishi mumkin. Agar belgi bo'yicha nomuvofiqlik
yuzaga kelsa x matnda, belgi uchun xato funktsiyasi jadvali x ko'rsatkichi bo'yicha
maslahat olinadi men nomuvofiqlik sodir bo'lgan naqshda. Bu bilan tugagan eng
uzun substring uzunligini qaytaradi men prefiksdan keyingi belgi bo'lishi sharti
bilan naqshning prefiksiga mos keladi x. Ushbu cheklash bilan belgi x matnda
keyingi bosqichda yana bir bor tekshirilishi shart emas va shuning uchun matnning
har bir indeksini qayta ishlash orasida faqat doimiy sonli amallar bajariladi[iqtibos
kerak]. Bu real vaqtda hisoblashning cheklanishini qondiradi.
Butning algoritmi ni topish uchun KMP oldindan ishlov berish funktsiyasining
o'zgartirilgan versiyasidan foydalanadi leksikografik jihatdan minimal burilish.
Xato funktsiyasi bosqichma-bosqich aylanayotganda hisoblab chiqiladi.
28

Birinchidan, muhim xususiyatga e'tibor bering: π [i] ≤ π [i - 1] +1. Ya'ni, keyingi
elementdagi prefiks funktsiyasi joriy elementdagi prefiks funktsiyasidan 1 dan
ortiq emas. π [i] = π [i - 1] +1 holatini tasvirlash oson:
2-rasm.
Ya'ni, quyidagi bayonot to'g'ri (0-indekslashda):
s [i] = s [ π [i - 1]] ⇒ π [i] = π [i - 1] +1
Bu holat juda ahamiyatsiz. Ammo s [i] ≠ s [ π [i − 1]] bo‘lsa-chi? Men j uzunligini
shunday topmoqchimanki, s [0..j − 1] = s [i − j..i − 1], lekin ayni paytda j < π [i −
1]. Agar s [i] = s [j] bo'lsa, π [i] = j + 1. Aslida j uzunligi prefiks funksiyasini
topish jarayonida allaqachon topilgan. Ya'ni, j = π [ π [i - 1] -1]. Grafik jihatdan bu
shunday ko'rinadi:
3-rasm.
29

$Agar j uzunligi ham mos kelmasa (s [i] ≠ s [j]), xuddi shu formuladan foydalanib, uni yana kamaytiring: j = π [j - 1]. Shunday qilib, j uzunlikdagi prefiksni j 0 ga teng bo'lguncha davom ettirishga harakat qilamiz. Bu holda s [i] ni s [0] bilan solishtirish kifoya qiladi va natijaga qarab π [i] = 0 yoki 1 ni belgilang. C++ da algoritmni amalga oshirish #include <iostream> #include <string> #include <vector > using namespace std ; string::size_type KMP( const string& S, int begin, const string& pattern) { vector<int> pf(pattern.length()); pf[0] = 0; for (int k = 0, i = 1; i < pattern.length(); ++i) { while ((k > 0) && (pattern[i] != pattern[k])) k = pf[k - 1]; if (pattern[i] == pattern[k]) k++; pf[i] = k; } for (int k = 0, i = begin; i < S.length(); ++i) { while ((k > 0) && (pattern[k] != S[i])) k = pf[k - 1]; if (pattern[k] == S[i])std::cout << k <<" \t " <<i+1 << " \t "; // kirishlarni ko'rish uchun k++; if (k == pattern.length()) return (i - pattern.length() + 1); // yoki keyingi hodisalarni qidirishda davom etamiz } return (string::npos); std::cout << string::npos; } int main() { 30$

setlocale(LC_ALL, "ru");
string pattern = "R а w";
string ss = "RjjruoyokiRawyoki";
int begin = 3;
KMP( ss, begin, pattern);
return 0;
}
Natija:
XULOSA
Prefiks funktsiyasi (n): Prefiks funktsiyasi, naqsh uchun n, naqshning o'zi siljishiga
qanday mos kelishi haqidagi bilimlarni qamrab oladi. Ushbu ma'lumot naqshning
foydasiz o'zgarishini oldini olish uchun ishlatilishi mumkin. Boshqacha qilib
aytadigan bo'lsak, bu "S" qatorining orqaga qaytishiga yo'l qo'ymaslik imkonini
beradi. Informatika sohasida Knuth-Morris-Pratt string-qidiruv algoritmi (yoki
KMP algoritmi) mos kelmaslik yuzaga kelganda so'zning o'zini o'zida
mujassamlashtirganini kuzatish orqali asosiy "matn qatori" S ichida "so'z" W ning
paydo bo'lishini qidiradi. Keyingi o'yin qaerda boshlanishi mumkinligini aniqlash
uchun etarli ma'lumot, shuning uchun. Algoritmning ikkita qismi mos ravishda
O(k) va O(n) murakkabliklariga ega bo lgani uchun umumiy algoritmningʻ
murakkabligi O(n+k) ga teng. Shunday qilib, KMP qidiruvining umumiy qiymati
31

satr va naqsh belgilarining soni bo'yicha chiziqli. Prefiks - so'z o'zagidan oldin
qo'yiladigan affiks. Uni bir so‘zning boshiga qo‘shish uni boshqa so‘zga
o‘zgartiradi. Masalan, baxtli so'zga un- prefiksi qo'shilsa, baxtsiz so'zini hosil
qiladi. ... Prefikslar, boshqa barcha affikslar kabi, odatda bog‘langan
morfemalardir. KMP algoritmi samarali e¬t naqsh izlash algoritmi bo'lib, naqshni
tez moslashtirish zarur bo'lgan joylarda qo'llaniladi, ammo kamchilik mavjud.
Turli naqshlar va matnlar uchun KMP bir necha marta qo'llanilishi kerak. Satrlarni
moslashtirish algoritmi bioinformatika, tarmoqqa kirishni aniqlash, kompyuter
viruslarini skanerlash va boshqalar kabi ko'plab amaliy sohalarda keng qo'llaniladi.
KMP (Knuth-Morris-Pratt) algoritmi katta hajmdagi matnlarga qo'llanganda
boshqa ko'plab qatorlarni moslashtirish algoritmlari bilan solishtirganda tez
bajarilishi uchun ishlatiladi. Biroq, kirish matni hajmi ma'lum chegaradan sezilarli
darajada oshganda, KMP algoritmining ishlashi cheklangan. Ushbu maqolada biz
umumiy maqsadli ko'p yadroli mikroprotsessor va OpenCL dan GPGPU (Grafik
ishlov berish yordamida umumiy maqsadli hisoblash) dan foydalangan holda
Grafik ishlov berish blokiga (GPU) asoslangan Heterojen yuqori samarali
hisoblash (HPC) arxitekturasida yuqori samarali parallel KMP algoritmini taklif
qilamiz. birlik) platformasi. Taklif etilayotgan parallel KMP algoritmi asosan
markaziy protsessor xotirasi va GPU xotirasi o'rtasidagi ma'lumotlar uzatishni
GPUdagi satrlarni moslashtirish operatsiyalari bilan qoplash orqali CPU-GPU
xotira ierarxiyasini optimallashtirishga qaratilgan. Shuningdek, u ishchi guruhlar
va ish elementlarini taqsimlashni optimallashtiradi va naqsh ma'lumotlari va
nosozliklar jadvalini GPUning chipdagi umumiy xotirasiga joylashtiradi.
Eksperimental natijalar shuni ko'rsatadiki, optimallashtirilgan parallel KMP
algoritmi bajarilish vaqtini ~8 baravar tezlashtiradi.
Foydalanilgan adabiyotlar
1. Knut, Donald; Morris, Jeyms X.; Pratt, Vaughan (1977). "Iplarga tez naqsh
solish". Hisoblash bo'yicha SIAM jurnali. 6 (2): 323–
350. CiteSeerX 10.1.1.93.8147 . doi : 10.1137/0206024 .
2. Knut, Donald E. (1973). "Kompyuter fanlari nazariyasining zarari". Mantiq va
matematikaning asoslari bo'yicha tadqiqotlar. 74 : 189–195. doi : 10.1016 / S0049-
237X (09) 70357-X . ISBN 9780444104915 .
3. Morris, JH, Jr; Pratt, V. (1970). Chiziqqa mos keladigan algoritm (Texnik
hisobot). Kaliforniya universiteti, Berkli, Hisoblash markazi. TR-40.
4. Matievich, Yuriy (1971). "O raspoznavanii v realnoe vremya otnosheniya
vxojdeniya" (PDF). Zapiski nauchnyx seminarlar Leningradskogo otdeleniya
Matematheskogo instituta im. V.A.Steklova (rus tilida). 20 : 104–114. sifatida ingliz
32

tiliga tarjima qilingan Matiyasevich, Yuriy (1973). "Qo'shish munosabatlarini real
vaqt rejimida tan olish" . Sovet matematikasi jurnali. 1 : 64–70. doi : 10.1007 /
BF01117471 .
5. Graham A.Stephen, “String Searching Algorithms”,year = 1994.
6. Donald Knuth, James H. Morris, Jr, Vaughan Pratt,“Fast pattern
matching in strings”, year = 1977.
7. Thomas H.Cormen; Charles E.Leiserson.,
Introduction to algorithms second edition , “The Knuth-Morris-Pratt
Algorithm”, year = 2001.
Internet resurslari:
1. https://en.wikipedia.org/wiki/Knuth .
2. https://www.coursera.org .
3. https://cp-algorithms.com .
33

Prefiks funksiyasi, uni hisoblash va qo‘lash. knut-moriss-pratt algoritmi

Купить

Похожие документы
3d-max dasturida obektlarni yaratish
Algoritm va ma’lumotlar strukturasi
3D-MAX dasturi haqida
3D Studio MAX dasturiga kirish. 3D Studio MAX dasturi haqida tushuncha
Adobe photoshop dasturida tasvirlarda ishlov berish,taqdimot yaratish

Информация о документе

Продавец

Prefiks funksiyasi, uni hisoblash va qo‘lash. knut-moriss-pratt algoritmi

Похожие документы