Function kmp_search 

pub fn kmp_search(text: &str, pattern: &str) -> Vec<usize>

KMP (Knuth–Morris–Pratt) — matndan namunani O(n + m) da qidirish.

Muammo: sodda qidiruvda moslik buzilganda biz boshiga qaytamiz va allaqachon o’qigan belgilarni qayta o’qiymiz.

KMP yechimi: namunaning o’zidan prefiks funksiyasi (LPS jadvali) tuzamiz: lps[i] = pattern[..=i] ning ham prefiks, ham suffiks bo’la oladigan eng uzun qismining uzunligi. Moslik buzilganda shu jadval bizga “qayerdan davom etish“ni aytadi — matn bo’yicha hech qachon orqaga qaytmaymiz.

 pattern: a b a b a c a
 lps:     0 0 1 2 3 0 1
                   ↑ "aba" ham bosh, ham oxir

• Time: O(n + m), Space: O(m).

Qaytadi: namunaning barcha boshlanish indekslari (belgilar bo’yicha).

Misol

use rust_algorithms::other::strings::kmp_search;

assert_eq!(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"), vec![10]);
assert_eq!(kmp_search("aaaaa", "aa"), vec![0, 1, 2, 3]);
assert_eq!(kmp_search("abc", "xyz"), Vec::<usize>::new());