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

II-bob.Z algaritmi amalga oshirish, satrini qidirish, misollar


2.1.Z algoritmining vaqt murakkabligi
Z algoritmining vaqt murakkabligi O(m+n) ga teng , bu yerda n izlanayotgan satr uzunligi va m izlanadigan naqsh uzunligi.
Uni quyidagicha hisoblash mumkin: Yangi yaratilgan satrimizning uzunligi m+n . Satrni bosib o'tish chiziqli vaqtni oladi, ya'ni = O (m + n)
Qachonki while tsikliga duch kelsak, faraz qilaylik, k ta amal bajarildi, lekin tashqi tsikllarning keyingi k takrori o'tkazib yuboriladi, chunki har safar yuqori chegara k ga oshiriladi.
Shunday qilib, Z massivini yaratish uchun sarflangan umumiy vaqt O(m+n) bo'lib qoladi .
Z massivida m ni qidirish uchun sarflangan vaqt ham O(m+n) vaqtini oladi .
Shunday qilib, umumiy vaqt murakkabligi: -
Z massivini yaratish uchun sarflangan umumiy vaqt O(m+n) qoladi + Z massivida m ni qidirish uchun sarflangan vaqt ham O(m+n) vaqtni oladi.
=O(m+n)+O(m+n)
=O(m+n)
2.2.Z algoritmini amalga oshirish
C/C++ da Z algoritmi
#include
using namespace std;
void create_Zarr(string str, int Z[])
{
int n = str.length();
int left, right, k;

// [left,right] make a window which matches with prefix of str

left = right = 0;
for (int i = 1; i < n; ++i)
{
// if i>right nothing matches so we will calculate.
// Z[i] using naive way.
if (i > right)
{
left = right = i;

// right-left = 0 in starting, so it will start

// checking from 0'th index.
while (rightright++;
Z[i] = right-left;
right--;
}
else
{
// k = i-left so k corresponds to number which
// matches in [left,right] interval.
k = i-left;

// if Z[k] is less than remaining interval

// then Z[i] will be equal to Z[k].
if (Z[k] < right-i+1)
Z[i] = Z[k];

else
{

// else start from right and check manually
left = i;
while (rightright++;
Z[i] = right-left;
right--;
}
}
}
}

void find(string text, string pattern)

{
// Create concatenated string "P$T with additional character"
string concat = pattern + "$" + text;
int l = concat.length();

// Constructing Z array

int Z[l];
create_Zarr(concat, Z);

// now looping through Z array for matching condition

for (int i = 0; i < l; ++i)
{
// if Z[i] (matched region) is equal to pattern
// length we got the pattern
if (Z[i] == pattern.length())
cout << "Pattern found at index "
<< i - pattern.length() -1 << endl;
}
}

// Driver program

int main()
{
string text = "faabbcdeffghiaaabbcdfgaabf";
string pattern = "aabb";
find(text, pattern);
return 0;
}
Chiqish
Pattern found at index 1
Pattern found at index 14
C++ kodini tushuntirish
Asosiy funktsiya bizning satrimiz va naqshimizdan iborat. Keyin topilma parametr sifatida satr va naqsh bilan chaqiriladi. Keling, find funktsiyasi ichida nima sodir bo'lishini ko'rib chiqaylik.
Find funksiyasi bajaradigan birinchi narsa, o'rtasida qo'shimcha $ belgisi bo'lgan string bilan naqshni birlashtirish orqali string konkatini yaratishdir . Endi biz ushbu satr uchun Z massivini yaratish uchun bu qatorni create_Zarr funksiyasiga uzatamiz . Keling, Z massivi qanday yaratilganligini ko'rib chiqaylik.
CreateZarr funksiyasida biz qiladigan birinchi narsa massivni yaratish uchun qidiruv oynasini saqlab qolish uchun chap va o'ng deb nomlangan ikkita o'zgaruvchini yaratishdir.
Chap va o'ng ikkalasi ham nolga tenglashtiriladi. Endi biz satrni kesib o'tishni va Z massivni to'ldirishni boshlaymiz. Z massivining birinchi qiymati hech qachon ishlatilmaydi va tayinlanmagan holda qoldirilishi mumkin. Endi biz joriy ko'rsatgichimiz i yoki yo'qligini tekshiramiz .
Agar u o'ngdan katta bo'lsa, bu biz hozirda oynadan tashqarida ekanligimizni anglatadi, shuning uchun biz ushbu indeksdagi Z qiymatini mos kelmaguncha har bir belgini birma-bir moslash orqali sodda satr moslashuvidan foydalanib hisoblaymiz. Bu qiymat joriy indeks uchun Z qiymatimizga aylanadi .
Agar joriy indeksimiz hozir oyna ichida bo'lsa, ya'ni o'ngdan kichikroq bo'lsa, biz k ni hisoblaymiz, bu bizning joriy indeksimizning oyna ichidagi o'rnini belgilaydi. Agar k indeksdagi Z qiymati o'ng-i+1 dan kichik bo'lsa, ya'ni k dan keyin oyna ichidagi elementlar soni , joriy indeksdagi Z qiymati k indeksdagi Z qiymatiga teng bo'ladi va oyna qoladi. bir xil.
Agar k indeksdagi Z qiymati o'ng-i+1 dan katta yoki teng bo'lsa , joriy oynani kengaytirish mumkin. Shunday qilib, biz left=i ni o'rnatamiz va avvalgidek satrni yana moslashni boshlaymiz. Satrni moslashtirgandan so'ng, joriy indeks Z[i] uchun bizning Z qiymatimiz o'ng-chap ga teng bo'ladi .
Concat string uchun Z massivi shunday yaratiladi. Endi satrda naqshning paydo bo'lishini topish uchun biz Z massivida naqsh uzunligiga teng qiymatni qidiramiz va agar u i indeksida topilsa, naqsh i-pattern_length-1 indeksida topilganligini chiqarishimiz mumkin (qo'shimchani olib tashlash). Z massivini yaratish uchun asl satrga uzunlik qo'shildi).