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

1.2.Z algoritmini tahlil qilish
Z algoritmini qo'llash uchun bizga izlanadigan qator va naqsh kerak bo'ladi.
Oldingi bo'limlarda aytib o'tilganidek, Z algoritmi satrda naqshning paydo bo'lishini topish uchun ishlatiladigan algoritmdir. Endi bu qanday ishlashini ko'rib chiqaylik.
Z algoritmi Z massivi deb nomlangan yordamchi massivni saqlash orqali ishlaydi. Bu Z massivi joriy indeksdan boshlab eng uzun pastki satr uzunligini saqlaydi, u ham prefiks. Bu shuni anglatadiki, har bir indeks ushbu indeksdan boshlab boshlang'ich belgilarga mos keladigan belgilar sonini saqlaydi. Bu shuni anglatadiki, agar Z massivida har qanday indeks uchun k qiymati bo'lsa , bu indeksdan keyingi k belgilar qatorning birinchi k belgisiga mos kelishini anglatadi . Bu Z algoritmining asosiy qismidir.
Z algoritmidan foydalanish uchun biz birinchi navbatda qidirish naqshini va qidiriladigan satrni birlashtiramiz va ular orasiga boshqa bir belgi qo'shamiz, bu hech qanday satrda mavjud emas. Keyin ushbu yangi yaratilgan qator uchun Z massivini yaratamiz .
Keyin biz Z massivini skanerlaymiz va uning qiymati izlanadigan naqsh uzunligiga teng bo'lgan har bir indeksda biz naqsh topilganligini aytamiz.
newString=pattern+'$'+string
bu erda $ satrda ham, naqshda ham mavjud bo'lmagan har qanday belgi bo'lishi mumkin.
Endi yuqorida aytib o'tilgan texnika nima uchun va qanday ishlashini tahlil qilish vaqti keldi. Avval Z massividan foydalanishni tushunib olaylik . Z massivi, har bir indeksda, satrning prefiksiga (boshlang'ich belgilar) mos keladigan, undan boshlanadigan eng uzun pastki qator uzunligini saqlaydi . Endi biz naqshni asl satrimizga qo'shimcha belgi bilan birlashtirganimizda, asosan biz yangi yaratilgan satrning prefiksi, ya'ni naqshimiz bilan satrning qolgan qismiga, ya'ni izlanadigan satrimizga mos kelamiz.
Hech bir satrimizda mavjud bo'lmagan qo'shimcha belgi qo'shganimiz sababli, bizning naqshimizdan uzunroq satr hech qachon topilmasligiga aminmiz.
Keling, buni quyidagi misol yordamida tushunaylik.
Misolda ko'rib turganimizdek, biz naqsh va satrni o'rtasiga qo'shimcha belgi bilan birlashtirdik, hech bir satrda mavjud emas. Endi biz Z massivini yaratganimizda , biz asosan satrimizning dastlabki 4 ta belgisini qidiramiz , bu ham bizning naqshimizdir. Biz qo'shimcha belgi qo'shganimiz sababli, biz topishimiz mumkin bo'lgan eng katta naqsh biz izlashimiz kerak bo'lgan naqsh bo'ladi. Endi Z massivini tahlil qilaylik .
Z massivining birinchi qiymati aniq nolga o'rnatiladi. 1-indeksdagi massivda ko'rib turganimizdek , 'a' indeksi 0('a') dagi belgi bilan mos kelganligi sababli , qiymat 1 ga o'rnatiladi . Keyin qiymatlarning hech biri mos kelmasa, ular nolga o'rnatiladi. Endi indeks 10 dagi qiymatni ko'rib chiqamiz . U 4 ga o'rnatiladi , chunki ushbu indeksdan boshlangan 4 ta belgi satrning prefiksiga mos keladi ( 4 ta belgidan boshlanadi).
Endi naqshning paydo bo'lishini topish uchun biz Z massivini skanerlaymiz va Z qiymati naqsh uzunligiga teng bo'lgan joyda naqsh topiladi, deb aytishimiz mumkin . Z algoritmi shunday ishlaydi.