Принсипи кори амалкарди алгоритми ҷустуҷӯи зерсатрҳои Кнут-Моррис-Пратта-ро шарҳ диҳед.
sobes.tech AI
Ҷавоб аз AI
Алгоритми Кнут-Моррис-Пратт (КМП) барои ҷустуҷӯи зерсатр дар сатр дар вақти хаттӣ пешбинӣ шудааст, ки муқоисаҳои такрорӣ бо ҳарфҳоро канор мегузорад.
Нақшаи асосӣ ин аст, ки барои зерсатр массиви функсияҳои префикс (ё "массив π") пешакӣ ҳисоб карда шавад, ки нишон медиҳад, ки чанд ҳарф бо оғози зерсатр дар муқоисаи номувофиқ мувофиқат мекунанд. Ин имкон медиҳад, ки дар ҳолати номувофиқат, ба ҷои баргаштан ба оғози сатр, зерсатрро ба миқдори оптималии ҷойҳо кӯчонем.
Масалан:
- Матн: "ABABDABACDABABCABAB"
- Ҷустуҷӯи зерсатр: "ABABCABAB"
Алгоритм аввал функсияи префиксро барои зерсатр месозад, сипас ба матн мегузарад ва ҳарфҳоро муқоиса мекунад. Дар ҳолати номувофиқат, аз функсияи префикс истифода мебарад, то муайян кунад, ки аз кадом ҳарфи зерсатр идома диҳад, бидуни оғоз аз оғоз.
Ин кафолат медиҳад, ки мураккабии O(n + m) дошта бошад, ки дар он n дарозии матн ва m дарозии зерсатр аст, ва аз ҷустуҷӯи оддӣ самараноктар аст.