Knuth-Morris-Pratt qidiruv algoritmining ishlash prinsipi haqida tushuntiring.
sobes.tech AI
AIdan javob
Knuth-Morris-Pratt (KMP) algoritmi matn ichida kichik qatorni qidirish uchun mo'ljallangan bo'lib, harflarni takroriy solishtirishdan qochadi.
Asosiy g'oya - kichik qator uchun avvaldan prefiks funktsiyalari massivini (yoki "π-massiv") hisoblash, bu massiv noto'g'ri solishtirishda kichik qator bilan mos kelgan belgilar sonini ko'rsatadi. Bu, mos kelmaslik holatida, asl matnning boshiga qaytib kelmasdan, kichik qatorni optimal miqdorda siljitishga imkon beradi.
Misol:
- Matn: "ABABDABACDABABCABAB"
- Qidirilayotgan kichik qator: "ABABCABAB"
Algoritm avval kichik qator uchun prefiks funktsiyasini tuzadi, so'ngra matn bo'ylab harflarni solishtirib o'tadi. Mos kelmaslik holatida, u prefiks funktsiyasidan foydalanib, qaysi belgidan solishtirishni davom ettirishni belgilaydi, boshlang'ichdan boshlamasdan.
Bu, O(n + m) murakkablikni ta'minlaydi; bu, oddiy qidiruvdan ko'ra samaraliroq.