Ներկայացրեք Knuth-Morris-Pratt ենթատող որոնման ալգորիթմի աշխատանքի սկզբունքը։
sobes.tech AI
Պատասխան AI-ից
Կնութ-Մորիս-Պրատտ (ԿՄՊ) ալգորիթմը նախատեսված է տեքստում ենթատեքստը որոնելու համար՝ ժամանակի գծային տեմպով, խուսափելով նիշերի կրկնվող համեմատություններից:
Հիմնական գաղափարը՝ նախապես հաշվարկել ենթատեքստի համար նախապատմական ֆունկցիաների զանգված (կամ «π-զանգված»), որը ցույց է տալիս, թե քանի նիշ է համընկնում ենթատեքստի սկզբին անհաջող համեմատության ժամանակ: Սա թույլ է տալիս, երբ համընկնում չկա, չվերադառնալ սկզբին, այլ տեղափոխել ենթատեքստը օպտիմալ թվով դիրքերում:
Օրինակ՝
- Տեքստը՝ "ABABDABACDABABCABAB"
- Փնտրում ենք ենթատեքստ՝ "ABABCABAB"
Ալգորիթմը նախ կառուցում է ենթատեքստի համար նախապատմական ֆունկցիան, ապա անցնում է տեքստով՝ համեմատելով նիշերը: Երբ համընկնում չկա, օգտագործում է նախապատմական ֆունկցիան՝ որոշելու համար, թե որ նիշից պետք է շարունակել համեմատությունը՝ առանց սկսելու սկզբից:
Այսպիսով՝ ապահովվում է O(n + m) բարդություն, որտեղ n տեքստի երկարությունն է, m՝ ենթատեքստի երկարությունը, և դա ավելի արդյունավետ է, քան naive որոնումը։