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

1.3.Z algoritmining ishlashi
Endi Z algoritmining ishlashini tushunamiz .
Avval Z algoritmi nima uchun oynadan foydalanishini tushunamiz . Z algoritmi Z massividagi oldingi qiymatlardan foydalangan holda uning bajarilishini tezlashtiradi va bu qiymatlar joriy oynaga muvofiq ishlatiladi. Joriy oyna ichida joriy uzunlikdan kattaroq satr bo'lishi mumkinligini tekshiramiz va agar buning iloji bo'lmasa, oyna ichidagi qolgan qiymatlar uchun hisob-kitobni o'tkazib yuboramiz.
Bu algoritmni juda tezlashtiradi, chunki ko'p elementlar o'tkazib yuboriladi. Agar bu usul ishlatilmasa, algoritm barcha elementlar uchun hisob-kitoblarni amalga oshiradi va shu bilan kvadratik [O() ga kamayadi.�2n2)] algoritmi, sodda namuna qidirishga teng.
Endi Z algoritmi uning bajarilishini tezlashtirish uchun oynadan qanday foydalanishini tushunamiz . Z algoritmi chap va o'ngdagi ikkita o'zgaruvchi o'rtasidagi oynani saqlaydi. Z massivini yaratishda ish faqat shu oyna ichida bajariladi va oyna yangilanib turadi. Endi biz oyna ichida bo'lganimizda, biz joriy elementlarning oyna ichidagi holatini topamiz, u k bo'lsin .
Keyin oynada k dan keyin elementlar sonini tekshiramiz va agar u k indeksdagi Z massividagi qiymatdan katta bo'lsa , joriy indeksdagi Z qiymati k indeksdagi Z qiymatiga teng bo'ladi .
Z algoritmidagi oyna bajarilishni tezlashtirish uchun shunday ishlatiladi. Oyna asosan Z massivining allaqachon to'ldirilgan qiymatlaridan foydalanadi.
Algoritm
Start
z_algo(search_string,pattern)
concatStr = concatenate pattern + “$” + text
patLen = length of pattern
n = length of concatStr
left = 0 and right = 0

for i = 1 to n, do

if i > right, then
left = i and right = i
while right < n AND concatStr[right-left]=concatStr[right], do
increase right by 1
done
ZArray[i] = right – left
decrease right by 1
else
k = i – left
if ZArray[k] < right – i +1, then
ZArray[i] = ZArray[k]
else
left = i
while right < n AND concatStr[right-left]=concatStr[right], do
increase right by 1
done
ZArray[i] = right – left
decrease right by 1

for i = 0 to n – 1, do

if ZArray[i] = patLen, then
print the location i – patLen – 1
End
Z algoritmi uning bajarilishini tezlashtirish uchun satrning avval skanerlangan qismidan foydalanadi. Biz mos keladigan prefikslar oynasini [chapga, o'ngga] saqlaymiz va nomuvofiqlik aniqlansa, oynani yangilaymiz.
Oynani saqlash bosqichlari -
Agar i > o'ng bo'lsa, i dan oldin boshlanib, i dan keyin tugaydigan prefiks pastki qatori yo'q , shuning uchun biz chap va o'ngni tiklaymiz va str[0..] ni str[i..] bilan taqqoslash orqali yangi [chap, o'ng] ni hisoblaymiz va olamiz. ZArray[i] = (o'ng-chap+1) .
Agar i <= o'ng bo'lsa, K = i-left bo'lsin , endi ZArray[i] >= min(Z[K], o'ng-i+1) , chunki str[i..] str[K..] bilan kamida mos keladi. o'ng-i+1 belgilar (ular [chap, o'ng] oraliqda, biz bilamizki, prefiks pastki qatori).
Endi ikkita kichik holat paydo bo'ladi - a) Agar ZArray[K] < o'ng-i+1 bo'lsa, str[i] dan boshlanadigan prefiks pastki qatori yo'q (aks holda ZArray[K ] kattaroq bo'lar edi), shuning uchun ZArray[i] = ZArray[K ] va interval [chap, o'ng] bir xil bo'lib qoladi. b) Agar ZArray[K] >= o'ng-i+1 bo'lsa, [chap, o'ng] oralig'ini uzaytirish mumkin , shuning uchun biz chapni i sifatida o'rnatamiz va str[o'ng] dan boshlab moslashni boshlaymiz va yangi o'ngga olamiz. yangilash oralig'i [chap, o'ng] va ZArray[i] = (o'ng-chap+1) hisoblang .
Quruq yugurish

Keling, String caabxaaab namunasini olamiz va aab naqshini qidiramiz . Biz qiladigan birinchi narsa eski satrlarni birlashtirib, yangi satr yaratishdir. Shunday qilib, yangi satr aab$caabxaaab ga aylanadi . Endi biz ushbu satr uchun Z massivini yaratamiz :
Z massividagi nol indeksidagi qiymat hech qanday foyda keltirmaydi, shuning uchun uni bo'sh qoldirish mumkin, shuning uchun biz 1-indeksdan boshlaymiz. Z_Array[1] 1 ga teng bo'ladi, chunki a boshlang'ich belgisi bilan faqat bitta belgi mos keladi va b mos kelmaslik.
Z_Array[2] nolga teng bo'ladi, chunki b boshlang'ich belgi bilan mos kelmaydi.
Z_Array[3] va Z_Array[4] ham nolga teng bo'ladi, chunki ikkalasi ham mos kelmaydi.
Z_Array[5] da biz moslikni topamiz, shuning uchun nomuvofiqlik topilmaguncha uni aniq qidirib hisoblaymiz. Z_Array[5] 3 bo'lib chiqadi. Shunday qilib, oyna [5,7] bo'ladi .
Z_Array[6] aniq hisoblanmaydi, chunki u oyna ichida va Z_Array[1] dan kattaroq bo'lgan elementlar soni . Shunday qilib, Z_Array[6] Z_Array[1] ga teng bo'ladi , ya'ni 1. Bu erda biz ilgari hisoblangan qiymatdan foydalandik.
Z_Array[7] ham hisoblanmaydi va Z_Array[2] ning oldingi qiymati Z_Array[7] uchun qiymat sifatida ishlatiladi .
Endi biz oldingi oynadan chiqamiz va 1 o'lchamdagi yangi oyna yaratiladi. Z_Array[8] aniq hisoblab chiqiladi va 1 bo'lib chiqadi.
Z_Array[9] da biz moslikni topamiz, shuning uchun nomuvofiqlik topilmaguncha uni aniq qidirib hisoblaymiz. Z_Array[9] 2 bo'lib chiqadi. Shunday qilib, oyna [9,11] bo'ladi .
Z_Array[10] oyna ichida, lekin uning oynadagi holatidagi Z qiymati, ya'ni Z[1] oynada qolgan elementlar sonidan kam emas. Shunday qilib, Z_Array[10] aniq hisoblab chiqilgan. Bu 3 bo'lib chiqadi. Oyna endi [10,12] ga aylanadi .
Z_Array[11] aniq hisoblanmaydi, chunki u oyna ichida va Z_Array[1] dan kattaroq bo'lgan elementlar soni . Shunday qilib, Z_Array[11] Z_Array[1] ga teng bo'ladi , ya'ni 1. Bu erda biz ilgari hisoblangan qiymatdan foydalandik.
Z_Array[12] ham hisoblanmaydi va Z_Array[2] ning oldingi qiymati Z_Array[12] uchun qiymat sifatida ishlatiladi .
Yakuniy Z massivi - _ 1 0 0 0 3 1 0 0 2 3 1 0
Z massivi shunday yaratilgan. Keyin biz qidiruv naqshining uzunligiga teng qiymatga ega indeksni qidiramiz va bizning elementimiz shu indeksda topiladi.