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

I-bob.Z algaritmini qo’llash va ishlashi
1.1.Z algoritmi (chiziqli vaqt namunasini qidirish algoritmi)
Ushbu algoritm chiziqli vaqt ichida matndagi naqshning barcha ko'rinishlarini topadi. Matn uzunligi n va naqsh uzunligi m bo'lsin, keyin olingan umumiy vaqt chiziqli fazo murakkabligi bilan O(m + n) bo'lsin. Endi biz vaqt va makon murakkabligi KMP algoritmi bilan bir xil ekanligini ko'rishimiz mumkin, ammo bu algoritmni tushunish osonroq.
Ushbu algoritmda biz Z massivini tuzamiz.
Z massivi nima?
str[0..n-1] qatori uchun Z massivi satr bilan bir xil uzunlikda. Z massivning Z[i] elementi str[0..n-1] prefiksi bo‘lgan str[i] dan boshlanadigan eng uzun pastki qator uzunligini saqlaydi. Z massivning birinchi yozuvi kamroq ma'noni anglatadi, chunki to'liq satr har doim o'zining prefiksi hisoblanadi.
Misol:
Indeks 0 1 2 3 4 5 6 7 8 9 10 11
Matn a a b c a a b x a a a z
Z qiymatlari X 1 0 0 3 1 0 0 2 2 1 0
Ko'proq misollar:
str = "aaaaaa"
Z[] = {x, 5, 4, 3, 2, 1}
str = "aabaacd"
Z[] = {x, 1, 0, 2, 1, 0, 0}
str = "abababab"
Z[] = {x, 0, 6, 0, 4, 0, 2, 0}
Z massivi chiziqli vaqtda naqsh izlashda qanday yordam beradi?
G‘oya naqsh va matnni birlashtirish va “P$T” qatorini yaratishdir, bunda P naqsh, $ maxsus belgi naqsh va matnda bo‘lmasligi kerak, T esa matndir. Birlashtirilgan qator uchun Z massivini yarating. Z massivida har qanday nuqtadagi Z qiymati naqsh uzunligiga teng bo'lsa, u holda naqsh mavjud.
Misol:
Shakl P = "aab", T matni = "baabaa"
Birlashtirilgan qator = "aab$baabaa"
Yuqoridagi birlashtirilgan satr uchun Z massivi {x, 1, 0, 0, 0,
3, 1, 0, 2, 1}.
Naqsh uzunligi 3 bo'lgani uchun Z massividagi qiymat 3 ga teng
naqsh mavjudligini ko'rsatadi.
Z massivini qanday qurish mumkin?
Oddiy yechim ikkita ichki halqani ishga tushirishdir, tashqi halqa har bir indeksga o'tadi va ichki halqa joriy indeksdan boshlab pastki qatorga mos keladigan eng uzun prefiks uzunligini topadi. Bu yechimning vaqt murakkabligi O(n2).
Z massivini chiziqli vaqtda qurishimiz mumkin.

G'oya, maksimal R bilan oraliq bo'lgan [L, R] oralig'ini saqlab qolishdir

shunday qilib, [L,R] prefiks pastki qatordir (pastki qator u ham prefiksdir).

Ushbu intervalni saqlab qolish uchun qadamlar quyidagicha:

1) Agar i > R bo'lsa, i va dan oldin boshlanadigan prefiks pastki qatori yo'q
i dan keyin tugaydi, shuning uchun biz L va R ni tiklaymiz va taqqoslash orqali yangi [L,R] ni hisoblaymiz
str[0..] dan str[i..] ga o'tkazing va Z[i] ni oling (= R-L+1).
2) Agar i <= R bo'lsa, K = i-L bo'lsin, endi Z[i] >= min(Z[K], R-i+1) chunki
str[i..] kamida R-i+1 belgilar uchun str[K..] bilan mos keladi (ular ichida
Biz bilgan [L,R] oralig'i prefiks pastki qatordir).
Endi ikkita kichik holat paydo bo'ladi -
a) Agar Z[K] < R-i+1 bo'lsa, u holda dan boshlanadigan prefiks pastki qator bo'lmaydi
str[i] (aks holda Z[K] kattaroq bo'lar edi) shuning uchun Z[i] = Z[K] va
[L,R] oralig'i bir xil bo'lib qoladi.
b) Z[K] >= R-i+1 bo'lsa, [L,R] oralig'ini kengaytirish mumkin
Shunday qilib, biz L ni i sifatida o'rnatamiz va str[R] dan boshlab moslashni boshlaymiz va
yangi R ni oling, keyin biz [L,R] oralig'ini yangilaymiz va Z[i] ni hisoblaymiz (=R-L+1).
Yuqoridagi bosqichma-bosqich protsedurani yaxshiroq tushunish uchun ushbu animatsiyani tekshiring - http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm
Algoritm chiziqli vaqtda ishlaydi, chunki biz hech qachon R dan kam belgilarni solishtirmaymiz va mos kelganda R ni bittaga oshiramiz, shuning uchun T taqqoslashlari mumkin. Mos kelmaslik holatida, har bir i uchun mos kelmaslik faqat bir marta sodir bo'ladi (shuning uchun R to'xtaydi), bu umumiy chiziqli murakkablikni keltirib chiqaradigan eng ko'p T taqqoslashdir.
Quyida naqsh izlash uchun Z algoritmining amalga oshirilishi keltirilgan.

// Naqsh qidirish uchun Z algoritmini amalga oshiradigan C++ dasturi

#include
std nom maydonidan foydalanish;
void getZarr(string str, int Z[]);

// Z algo yordamida matndagi barcha naqshlarni chop etadi

qidiruvni bekor qilish (satr matni, string naqsh)
{
// "P$T" birlashtirilgan qatorni yarating
string concat = naqsh + "$" + matn;
int l = concat.length();
// Z massivini tuzing
int Z[l];
getZarr(concat, Z);
// mos keluvchi shart uchun Z massivida aylanish
uchun (int i = 0; i < l; ++i)
{
// agar Z[i] (mos keladigan hudud) naqshga teng bo'lsa
// uzunligi biz naqshni oldik
agar (Z[i] == pattern.length())
cout << "Indeksda namuna topilgan"
<< i - pattern.length() -1 << endl;
}
}

// Berilgan str[] qatori uchun Z massivini to'ldiradi

void getZarr(string str, int Z[])
{
int n = str.length();
int L, R, k;

// [L,R] s prefiksi bilan mos keladigan oyna yarating

L = R = 0;
uchun (int i = 1; i < n; ++i)
{
// agar i>R hech narsa mos kelmasa, biz hisoblaymiz.
// Z[i] sodda usul yordamida.
agar (i > R)
{
L = R = i;

// Boshlanishda R-L = 0, shuning uchun u boshlanadi

// 0-indeksdan tekshirish. Masalan,
// "ababab" uchun