Bizda quyidagi matn bor bo’lsin

Xeshlashdan yana bir foydalanish: Rabin-Karp string qidiruvi

Xeshlashning yana bir qo'llanilishi: Rabin-Karp string qidiruvi
Biz ko'p ko'rib chiqmagan va ushbu qo'llanmada faqat qisqacha to'xtalib o'tadigan muammo - bu satrni qidirish, boshqa satr ichida satrni topish muammosi. Misol uchun, matn protsessoringizda "Topish" buyrug'ini bajarganingizda, dasturingiz barcha matnni o'z ichiga olgan satr boshidan boshlanadi (hozircha faraz qilaylik, matn protsessoringiz matningizni shunday saqlaydi, ehtimol u buni saqlamaydi). 't) va ushbu matn ichida siz ko'rsatgan boshqa qatorni qidiradi.
Satrlarni qidirishning eng asosiy usuli "qo'pol kuch" usuli deb ataladi. Shafqatsiz kuch usuli - bu muammoning barcha mumkin bo'lgan echimlarini izlash. Har bir mumkin bo'lgan yechim ishlayotgani topilmaguncha sinovdan o'tkaziladi.

Stringni qo'pol kuch bilan qidirish

Biz qidirilayotgan satrni “matn satri” va izlanayotgan satrni “naqsh qatori” deb ataymiz. Qo'pol qidiruv algoritmi quyidagicha ishlaydi: 1. Matn qatorining boshidan boshlang. 2. Matn satrining birinchi n ta belgisini (bu yerda n - naqsh qatorining uzunligi) naqsh qatori bilan solishtiring. Ular mos keladimi? Ha bo'lsa, biz tugatdik. Agar yo'q bo'lsa, davom eting. 3. Matn satrining bir joyiga siljiting. Birinchi n ta belgi mos keladimi? Ha bo'lsa, biz tugatdik. Agar yo'q bo'lsa, matn qatorining oxiriga yetguncha yoki mos keladigan topilgunimizcha ushbu qadamni takrorlang.

Uning kodi quyidagicha ko'rinadi:
int bfsearch(char* naqsh, char* matn) { int naqsh_len, takroriy sonlar, i; /* Agar satrlardan biri NULL bo'lsa, satr * topilmaganligini qaytaring. */ agar (naqsh == NULL || matn == NULL) -1ni qaytaradi; /* Satr uzunligini oling va qancha turli joylarni aniqlang * ularni solishtirish uchun matn satriga naqsh satrini qo'yishimiz mumkin. */ pattern_len = strlen (naqsh); takrorlashlar soni = strlen (matn) - naqsh_len + 1; /* Har bir joy uchun satrlarni taqqoslang. Agar satr topilsa, * matn satrida u joylashgan joyni qaytaring. */ for (i = 0; i < num_iterations; i++) { if (!strncmp(pattern, &(matn[i]), pattern_len)) return i; } /* Aks holda, naqsh topilmaganligini bildiring */ return -1; }
Bu ishlaydi, lekin biz ilgari ko'rganimizdek, shunchaki ishlash etarli emas. Shafqatsiz qidiruvning samaradorligi qanday? Xo'sh, biz har safar satrlarni solishtirganda, biz M taqqoslashni amalga oshiramiz, bu erda M - naqsh chizig'ining uzunligi. Va biz buni necha marta qilamiz? N marta, bu erda N - matn qatorining uzunligi. Shunday qilib, qo'pol kuch bilan string qidirish O ( MN ) dir . Unchalik yaxshi emas.
Qanday qilib biz yaxshiroq qila olamiz?