Magyarázza el a Knuth-Morris-Pratt alalgoritmus alrendszerének működési elvét.
sobes.tech MI
Válasz az MI-től
A Knuth-Morris-Pratt (KMP) algoritmus célja, hogy egy sztringben lineáris idő alatt keressen egy al-sztringet, elkerülve a karakterek ismételt összehasonlítását.
A fő ötlet az, hogy előre kiszámítson egy prefix-függvény tömböt (vagy "π-tömböt") az al-sztringhez, amely megmutatja, hány karakter egyezik az al-sztring kezdetével egy sikertelen összehasonlítás során. Ez lehetővé teszi, hogy össze nem egyezés esetén ne térjünk vissza az eredeti sztring elejére, hanem az al-sztringet a lehető legoptimálisabb pozícióba mozgassuk.
Példa:
- Szöveg: "ABABDABACDABABCABAB"
- Keresett al-sztring: "ABABCABAB"
A algoritmus először elkészíti az prefix-függvényt az al-sztringhez, majd végigmegy a szövegen, összehasonlítva a karaktereket. Nem egyezés esetén a prefix-függvényt használva meghatározza, hogy melyik karaktertől folytassa az összehasonlítást, anélkül, hogy az elejéről kezdené.
Ez garantálja az O(n + m) összetettséget, ahol n a szöveg hossza, m az al-sztring hossza, és hatékonyabb, mint az egyszerű keresés.