O’zbekiston respublikasi

Asosiy qism:
Algoritm


Mos kelishmovchiliklar qizil rang bilan belgilangan. Tegishli namunaviy indeks jadvalga mos kelmaslik raqamiga ko'ra yoziladi , ya'ni va hokazo.
Algoritm haqida tushuncha va malumotlar.
Tahlil namuna bilan matn nomuvofiqliklari haqidagi ma'lumotlarni o'z ichiga olgan ikki o'lchovli matn nomuvofiqliklaridan foydalanadi . Tahlil qilish tugallangach, uning birinchi qatori va satrlari orasidagi birinchi nomuvofiqlikdagi pozitsiyalarni o'z ichiga oladi . Shunday qilib, agar , u holda , va chapdan o'ngga sanab, va o'rtasidagi mos kelmaslikdir . Agar pastki qator nomuvofiqliklar soni dan kam bo'lsa , dan boshlab qatorning elementlari standart qiymatga teng bo'ladi . (Misolga qarang ) .
E'tibor bering, agar bo'lsa , u holda pastki qator namunadan belgilardan ko'p bo'lmagan farq qiladi va shuning uchun muammoning echimi hisoblanadi.
Keyin naqsh matnga parallel ravishda chapdan o'ngga, bir vaqtning o'zida bir belgidan skanerlanadi. Iteratsiyada pastki qator naqsh bilan taqqoslanadi . Oldingi iteratsiyalar davomida erishilgan matnning eng o'ng pozitsiyasi bo'lsin , ya'ni bu raqamlarning maksimali , bu erda . Agar , to ga va orasidagi nomuvofiqliklar sonini topuvchi amal natijasi tayinlanadi . Agar dan oshmasa , matnning mos kelmasligi jadvali o'zgartiriladigan va pastki qatorlarni taqqoslaydigan protsedura chaqiril-adi . O'zgar-uvchi quyida muhokama qilinadi.



protsedurani uzaytirish

Keling, protsedurani batafsil ko'rib chiqaylik. U pastki satrlarni solishtiradi va agar mos kelsa, ko'paytiriladi va matn nomuvofiqliklari jadvali yangilanadi. Bu hech qanday nomuvofiqliklar topilmaguncha ( iteratsiyada ilgari topilgan nomuvofiq-liklarni hisobga olgan holda ) yoki nomuvofiqliklardan ko'pi bilan erishil-maguncha , ya'ni bilan boshlanadigan naqsh paydo bo'lguncha sodir bo'ladi .



birlashtirish tartibi

Keling, protsedurani batafsil ko'rib chiqaylik. U va orasidagi tafovutlar sonini topadi va ilgari olingan ma'lumotlardan foydalanib, uni topilgan raqamga tenglash-tiradi. Kiramiz - bu nomuvofiqlik jadvalining qatori bo'lib, unda namunaning boshini va ni birlashtirish natijasida olingan nomuvofiqliklar haqidagi ma'lumotlar mav-jud . Hozirgacha tekshirilgan eng o'ngdagi matn pozitsiyasining joriy raqami . Shuning uchun, bilan boshlanadigan pastki satrga ishlov berishda, bilan mos keladigan naqsh haqidagi ma'lumotlarni o'z ichiga olgan qatordagi ma'lumotlarni hisobga olishingiz mumkin . Mos kelmaydigan jadvaldagi mos qiymatlar shunday bo'ladi, buning uchun butun sonlarning eng kichigi qayerda ?. Biroq, shuni yodda tutingki, bu nomuvofiqliklar naqshning boshlanishiga to'g'ri keladi, u bilan tekislangan edi , naqshning joriy holati esa joylashuvdagi farq bilan mos keladi .
Algoritm, shuningdek , namunani oldindan qayta ishlash bosqichida yaratil-gan namunaviy mos kelmasliklarning ikki o'lchovli qatoridan foydalanadi . U turli xil siljishlarda naqsh va o'zi o'rtasidagi nomuvofiqlik pozitsiyalarini o'z ichiga oladi, xuddi shunga o'xshash , ya'ni qator pastki qatorlar va pastki satrlar orasi-dagi birinchi mos kelmaslik ichidagi pozitsiyalarni o'z ichiga oladi . Shunday qilib, agar , u holda , va o'rtasidagi va chapdan o'ngga mos kelmasligi . Agar bu qatorlar orasidagi nomuvofiqliklar soni dan kam bo'lsa , dan boshlab , th qator ele-mentlari standart qiymatga teng bo'ladi. Qurilish keyinroq batafsilroq muhokama qilinadi.

Shunday qilib, naqsh nomuvofiqligi jadvalining qatori qiymatlardan foydalangan holda qiziqish uyg'otadi, bu erda eng to'g'ri nomuvofiqlik qaerda , chunki pastki satrda faqat mos kelmaslik talab qilinadi .
Ko'rsatilgan ma'lumotni protsedurada ishlatish uchun matndagi diapazondagi pozitsiyani ko'rib chiqing . Lavozim uchun quyidagi shartlarni ko'rib chiqing :
A sharti : belgilar va moslashtirilganda, matndagi pozitsiya naqsh va matn o'rtasidagi oldindan aniqlangan nomuvofiqlikka mos keladi, ya'ni va bu nomuvofiqlik raqami , bu erda , ya'ni .

B sharti : naqshning ikki nusxasi uchun, bir-biridan ofset , matn bilan tekislangan, shunda ularning boshlang'ich belgilari yuqorida yotadi va mos ravishda , pozitsiya ikki naqsh o'rtasidagi nomuvofiqlikka mos keladi, ya'ni . Bu ushbu smenadagi -th nomuvofiqligi, bu erda , ya'ni

Eslatib o'tamiz, bizni pozitsiyadagi matn belgisi bilan birlashganda mos keladigan naqsh belgisiga mos keladimi yoki yo'qligi qiziqtiradi , ya'ni bu rostmi ? Keling, bu savolni yuqoridagi shartlarning turli kombinatsiyalarida ko'rib chiqaylik.
1-holat: !A va !B: Ya'ni, va , qaerdan . Matn belgisini naqsh belgisi bilan solishtirishning hojati yo'q, chunki ular o'sha holatda mos kelishi aniq.
2-holat: (A va !B) yoki (!A va B): Har qanday holatda ham (agar faqat A sharti to'g'ri bo'lsa, u holda va , shuning uchun , boshqa tomondan, agar faqat B sharti bajarilsa , u holda ikkala , va yana , ). Oldingi holatda bo'lgani kabi, matn belgisini naqsh belgisi bilan solishtirishning hojati yo'q, chunki ular mos kelmasligi ma'lum.
3-holat: A va B: Bu holda va belgilar bir xil yoki yo'qligini ayta olmaymiz , shuning uchun ularni solishtirish kerak.
Biz protseduraga qaytamiz . 2 - holatda yoki 3-holatda belgilar nomuvofiqligi mavjud bo'lsa, belgilar nomuvofiqliklari sonini bittaga oshiring va yangilang . Jadvalning mos qiymatlari va . O'zgaruvchilar va dastlab ushbu ikki massivning birinchi elementlarining indekslariga mos ravishda o'rnatiladi va ketma-ket oshiriladi.
Jarayonni tugatish shartlari quyidagilardan iborat:
Agar bo'lsa , namuna matnga mos keladigan tarzda joylashgan bo'lsa , nomuvofiqlik aniqlanadi, shuning uchun protseduradan chiqish mumkin.Eslatib o'tamiz, bizni qiziqtirgan pozitsiyalarning eng o'ng tomoni , ya'ni , if ga teng , shuning uchun u ning oldingi qiymati uchun ishlatiladi , ya'ni , va shuning uchun pozitsiyani o'tkazib yuborish kerak. Shuning uchun, bu holatda protseduradan chiqish ham mumkin.Agar va bo'lsa protsedura to'xtatilishi mumkin . Agar ushbu shartning ikkinchi qismi bajarilsa, u holda teng bo'ladi va keyingi qiymatlar uchun yig'indilarga mos keladi . Bunday holda, agar yuqoridagi shartning birinchi qismi ham bajarilsa, protsedura to'xtatilishi mumkin, chunki bu matn pozitsiyasi aslida o'tkazib yuborilganligini ko'rsatadi.
Namunaviy nomuvofiqlik jadvalidagi nomuvofiq pozitsiyalar soni hammasini yoki agar ko'proq bo'lsa, birinchi nomuvofiqliklarni topish uchun etarli ekanligini ko'rsatish qoladi . Buni quyidagicha ko'rsatish mumkin. A sharti faqat matnning diapazondagi joylashuvi uchun qondiriladi . B sharti bir xil oraliqdagi noma'lum sonli pozitsiyalar uchun bajariladi. Naqshning mos kelmasligi jadvalidagi qator , , mos keladigan ofset bilan naqshning ikki nusxasi orasidagi nomuvofiqlik pozitsiyalarini o'z ichiga oladi . Agar bo'lsa , jadvalda namunaning o'zi bilan mos kelmasligining barcha pozitsiyalari mavjud bo'lib, ular uchun B sharti mavjudintervaldagi matn pozitsiyalari uchun amalga oshiriladi . Boshqa tomondan, agar bo'lsa ,jadval B sharti qanoatlantirilgan diapazondagi matn pozitsiyalarini beri-shi mumkin . Chunki A sharti to'g'ri bo'lgan diapazonda matn pozitsiyalari mav-jud . Shunday qilib, eng yomon holatda, 3 -holat sodir bo'lgan va to'g'ridan-to'g'ri solishtirish kerak bo'lgan pozitsiyalar bo'lishi mumkin. Hech bo'lmaganda B shartini qondiradigan, ammo A shartini qondirmaydigan pozitsiyalar mavjud ( 2-holat), bu matnga nisbatan naqshning ma'lum bir pozitsiyasi uchun matn va naqsh o'rtasida kamida shuncha ko'p nomuvofiqliklar mavjud degan xulosaga kelish uchun etarli.