Knuth-Morris-Pratt субсөздөрдү издөө алгоритмин иштөө принцибин түшүндүрүңүз.
sobes.tech AI
AIден жооп
Knuth-Morris-Pratt (KMP) алгоритми, символдорду кайра-кайра салыштырбай, жолдо поджолду табуу үчүн түзүлгөн, линиялык убакытта иштейт.
Негизги идея — поджол үчүн алдын ала префикс функциялары массивин (же "π-массив"), эсептеп чыгуу, ал салыштыруу учурунда неудачно болгон учурда, поджолдун башталышына канча символ туура келгенин көрсөтөт. Бул, туура келбеген учурда, оригиналдуу жолго кайтып барбай, поджолду оптималдуу орунга жылдырууга мүмкүндүк берет.
Мисал:
- Текст: "ABABDABACDABABCABAB"
- Издөөчү поджол: "ABABCABAB"
Алгоритм биринчи префикс функциясын түзөт, андан кийин текстти өтүп, символдорду салыштырат. Туура келбеген учурда, префикс функциясын колдонуп, кайсы символдон салыштыруу улантыла турганын аныктайт, баштан баштабай.
Бул, O(n + m) татаалдыгын камсыз кылат, анда n — тексттин узундугу, m — поджолдун узундугу, жана бул наивдүү издөөгө караганда натыйжалуу.