Објасните принцип рада алгоритма за претрагу подстринга Кнут-Морис-Прат.
sobes.tech АИ
Одговор од АИ
Algoritam Knuth-Morris-Pratt (KMP) je osmišljen za pronalaženje podniza u nizu u linearnom vremenu, izbegavajući ponovljena poređenja karaktera.
Glavna ideja je prethodno izračunati za podniz niz funkcija prefiksa (ili "π-niz"), koji pokazuje koliko karaktera se poklapa sa početkom podniza pri neuspešnom poređenju. Ovo omogućava, u slučaju neusaglašenosti, da se ne vraćamo na početak izvornog niza, već da pomerimo podniz za optimalan broj pozicija.
Primer:
- Tekst: "ABABDABACDABABCABAB"
- Traženi podniz: "ABABCABAB"
Algoritam prvo gradi funkciju prefiksa za podniz, zatim prolazi kroz tekst, poredeći karaktere. U slučaju neusaglašenosti, koristi funkciju prefiksa da odredi od kojeg karaktera podniza da nastavi poređenje, bez ponovnog početka.
Ovo obezbeđuje složenost O(n + m), gde je n dužina teksta, m dužina podniza, i efikasnije je od naivnog pretraživanja.