Izskaidrojiet Knuth-Morris-Pratt apakšvirknes meklēšanas algoritma darbības principu.
sobes.tech AI
Atbilde no AI
Knuth-Morris-Pratt (KMP) algoritms ir paredzēts, lai meklētu apakšvirkni teksta virknes laikā, izvairoties no atkārtotiem rakstzīmju salīdzinājumiem.
Galvenā ideja ir iepriekš aprēķināt apakšvirknes prefiksa funkciju masīvu (vai "π-masīvu"), kas rāda, cik rakstzīmes sakrīt ar apakšvirknes sākumu neveiksmīgas salīdzināšanas gadījumā. Tas ļauj, neatrodoties uz sākuma teksta, pārvietot apakšvirkni uz optimālo pozīciju.
Piemērs:
- Teksts: "ABABDABACDABABCABAB"
- Meklējam apakšvirkni: "ABABCABAB"
Algoritms vispirms izveido prefiksa funkciju apakšvirknei, pēc tam pārbauda tekstu, salīdzinot rakstzīmes. Nesaistības gadījumā izmanto prefiksa funkciju, lai noteiktu, no kura rakstzīmes turpināt salīdzinājumu, nesākot no sākuma.
Tas nodrošina O(n + m) sarežģītību, kur n ir teksta garums, m — apakšvirknes garums, un tas ir efektīvāk nekā naivā meklēšana.