rust_algorithms/other/

strings.rs

//! Satrlar bilan ishlash algoritmlari.
//!
//! > **Rust eslatmasi:** `String` — UTF-8. `s[0]` ishlamaydi, chunki bitta belgi
//! > 1–4 bayt bo'lishi mumkin. Shu sababli bu yerdagi funksiyalar `Vec<char>` bilan
//! > ishlaydi — o'zbekcha `oʻ`, `gʻ` kabi belgilar ham to'g'ri hisoblanadi.

use std::collections::HashMap;

/// Sodda (naive) qidiruv: har bir pozitsiyadan boshlab solishtirish.
///
/// - **Time:** eng yomon holatda O(n·m), **Space:** O(1).
///
/// # Misol
/// ```
/// use rust_algorithms::other::strings::naive_search;
///
/// assert_eq!(naive_search("abcabcabd", "abcabd"), vec![3]);
/// assert_eq!(naive_search("aaaa", "aa"), vec![0, 1, 2]);
/// ```
pub fn naive_search(text: &str, pattern: &str) -> Vec<usize> {
    let t: Vec<char> = text.chars().collect();
    let p: Vec<char> = pattern.chars().collect();
    if p.is_empty() || p.len() > t.len() {
        return Vec::new();
    }
    (0..=(t.len() - p.len()))
        .filter(|&i| t[i..i + p.len()] == p[..])
        .collect()
}

/// **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**.
///
/// ```text
///  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());
/// ```
pub fn kmp_search(text: &str, pattern: &str) -> Vec<usize> {
    let t: Vec<char> = text.chars().collect();
    let p: Vec<char> = pattern.chars().collect();
    if p.is_empty() || p.len() > t.len() {
        return Vec::new();
    }

    let lps = prefix_function(&p);
    let mut natija = Vec::new();
    let mut j = 0usize; // namunada nechta belgi mos keldi

    for (i, &ch) in t.iter().enumerate() {
        while j > 0 && ch != p[j] {
            j = lps[j - 1]; // orqaga qaytmasdan "sakraymiz"
        }
        if ch == p[j] {
            j += 1;
        }
        if j == p.len() {
            natija.push(i + 1 - p.len());
            j = lps[j - 1]; // keyingi mosliklarni ham qidiramiz
        }
    }
    natija
}

/// KMP uchun prefiks funksiyasi (LPS jadvali).
fn prefix_function(p: &[char]) -> Vec<usize> {
    let mut lps = vec![0usize; p.len()];
    let mut k = 0usize;
    for i in 1..p.len() {
        while k > 0 && p[i] != p[k] {
            k = lps[k - 1];
        }
        if p[i] == p[k] {
            k += 1;
        }
        lps[i] = k;
    }
    lps
}

/// **Rabin-Karp** — xesh yordamida qidirish (rolling hash).
///
/// **G'oya:** namunaning xeshini hisoblaymiz va matn bo'ylab siljuvchi oynaning
/// xeshini **O(1)** da yangilaymiz (chiqqanini ayirib, kirganini qo'shib).
/// Xeshlar teng bo'lsa — haqiqiy tenglikni tekshiramiz (soxta moslik bo'lishi mumkin).
///
/// - **Time:** o'rtacha O(n + m), eng yomon holatda O(n·m).
/// - **Kuchli tomoni:** bir vaqtda **ko'p namunani** qidirishga oson kengayadi
///   (plagiat tekshirgichlar shu tamoyilda ishlaydi).
///
/// # Misol
/// ```
/// use rust_algorithms::other::strings::{kmp_search, rabin_karp};
///
/// let matn = "the quick brown fox jumps over the lazy dog";
/// assert_eq!(rabin_karp(matn, "the"), kmp_search(matn, "the"));
/// assert_eq!(rabin_karp(matn, "fox"), vec![16]);
/// ```
pub fn rabin_karp(text: &str, pattern: &str) -> Vec<usize> {
    const ASOS: u64 = 256;
    const MOD: u64 = 1_000_000_007;

    let t: Vec<char> = text.chars().collect();
    let p: Vec<char> = pattern.chars().collect();
    if p.is_empty() || p.len() > t.len() {
        return Vec::new();
    }

    // eng yuqori razryad koeffitsienti: ASOS^(m-1) mod MOD
    let mut yuqori = 1u64;
    for _ in 1..p.len() {
        yuqori = yuqori * ASOS % MOD;
    }

    let xesh = |belgilar: &[char]| -> u64 {
        belgilar
            .iter()
            .fold(0u64, |acc, &c| (acc * ASOS + c as u64) % MOD)
    };

    let p_xesh = xesh(&p);
    let mut oyna = xesh(&t[..p.len()]);
    let mut natija = Vec::new();

    for i in 0..=(t.len() - p.len()) {
        if oyna == p_xesh && t[i..i + p.len()] == p[..] {
            natija.push(i);
        }
        if i + p.len() < t.len() {
            // chiqqan belgini ayiramiz, yangisini qo'shamiz
            let chiqdi = t[i] as u64 % MOD * yuqori % MOD;
            oyna = (oyna + MOD - chiqdi) % MOD;
            oyna = (oyna * ASOS + t[i + p.len()] as u64) % MOD;
        }
    }
    natija
}

/// Satr palindrommi? (harf-raqamlardan boshqasi e'tiborga olinmaydi, registr muhim emas)
///
/// - **Time:** O(n), **Space:** O(n).
///
/// # Misol
/// ```
/// use rust_algorithms::other::strings::is_palindrome;
///
/// assert!(is_palindrome("kavak"));
/// assert!(is_palindrome("A man, a plan, a canal: Panama"));
/// assert!(!is_palindrome("salom"));
/// assert!(is_palindrome(""));
/// ```
pub fn is_palindrome(s: &str) -> bool {
    let tozalangan: Vec<char> = s
        .chars()
        .filter(|c| c.is_alphanumeric())
        .flat_map(|c| c.to_lowercase())
        .collect();

    let (mut chap, mut ong) = (0usize, tozalangan.len());
    while chap + 1 < ong {
        if tozalangan[chap] != tozalangan[ong - 1] {
            return false;
        }
        chap += 1;
        ong -= 1;
    }
    true
}

/// Ikki satr anagrammi? (bir xil harflardan tuzilganmi)
///
/// - **Time:** O(n + m), **Space:** O(alifbo).
///
/// # Misol
/// ```
/// use rust_algorithms::other::strings::is_anagram;
///
/// assert!(is_anagram("listen", "silent"));
/// assert!(is_anagram("olma", "malo"));
/// assert!(!is_anagram("salom", "salomat"));
/// ```
pub fn is_anagram(a: &str, b: &str) -> bool {
    fn sanoq(s: &str) -> HashMap<char, usize> {
        let mut m = HashMap::new();
        for c in s.chars().flat_map(|c| c.to_lowercase()) {
            *m.entry(c).or_insert(0) += 1;
        }
        m
    }
    sanoq(a) == sanoq(b)
}

/// Satrlar to'plamining eng uzun umumiy prefiksi.
///
/// - **Time:** O(jami belgilar soni).
///
/// # Misol
/// ```
/// use rust_algorithms::other::strings::longest_common_prefix;
///
/// assert_eq!(longest_common_prefix(&["flower", "flow", "flight"]), "fl");
/// assert_eq!(longest_common_prefix(&["dog", "car"]), "");
/// assert_eq!(longest_common_prefix(&[]), "");
/// ```
pub fn longest_common_prefix(words: &[&str]) -> String {
    let Some(birinchi) = words.first() else {
        return String::new();
    };
    let mut prefiks: Vec<char> = birinchi.chars().collect();

    for so_z in &words[1..] {
        let belgilar: Vec<char> = so_z.chars().collect();
        let mut i = 0;
        while i < prefiks.len() && i < belgilar.len() && prefiks[i] == belgilar[i] {
            i += 1;
        }
        prefiks.truncate(i);
        if prefiks.is_empty() {
            break;
        }
    }
    prefiks.into_iter().collect()
}

/// So'zlar tartibini teskari qiladi ("Men Rust yaxshi ko'raman" → "ko'raman yaxshi Rust Men").
///
/// # Misol
/// ```
/// use rust_algorithms::other::strings::reverse_words;
///
/// assert_eq!(reverse_words("Men Rustni yaxshi ko'raman"), "ko'raman yaxshi Rustni Men");
/// assert_eq!(reverse_words("  bir   ikki  "), "ikki bir");
/// ```
pub fn reverse_words(s: &str) -> String {
    s.split_whitespace().rev().collect::<Vec<_>>().join(" ")
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::util::Rng;

    #[test]
    fn uchta_qidiruv_bir_xil_natija() {
        let mut rng = Rng::new(1201);
        let alifbo = ['a', 'b', 'c'];
        for _ in 0..100 {
            let matn: String = (0..60).map(|_| alifbo[rng.below(3)]).collect();
            let namuna: String = (0..(1 + rng.below(4)))
                .map(|_| alifbo[rng.below(3)])
                .collect();

            let n = naive_search(&matn, &namuna);
            assert_eq!(kmp_search(&matn, &namuna), n, "matn={matn} namuna={namuna}");
            assert_eq!(rabin_karp(&matn, &namuna), n);
        }
    }

    #[test]
    fn chegaraviy_holatlar() {
        assert!(kmp_search("", "a").is_empty());
        assert!(kmp_search("a", "").is_empty());
        assert!(kmp_search("ab", "abc").is_empty());
        assert_eq!(kmp_search("abc", "abc"), vec![0]);
    }

    #[test]
    fn prefiks_funksiyasi() {
        let p: Vec<char> = "ababaca".chars().collect();
        assert_eq!(prefix_function(&p), vec![0, 0, 1, 2, 3, 0, 1]);
    }

    #[test]
    fn palindromlar() {
        assert!(is_palindrome("a"));
        assert!(is_palindrome("aa"));
        assert!(is_palindrome("aba"));
        assert!(!is_palindrome("ab"));
        assert!(is_palindrome("No 'x' in Nixon"));
    }

    #[test]
    fn anagrammalar() {
        assert!(is_anagram("", ""));
        assert!(is_anagram("Aabb", "bBAa"));
        assert!(!is_anagram("aab", "abb"));
    }

    #[test]
    fn umumiy_prefiks() {
        assert_eq!(longest_common_prefix(&["a"]), "a");
        assert_eq!(longest_common_prefix(&["", "abc"]), "");
        assert_eq!(longest_common_prefix(&["abc", "abc"]), "abc");
    }

    #[test]
    fn sozlarni_teskarilash() {
        assert_eq!(reverse_words(""), "");
        assert_eq!(reverse_words("bitta"), "bitta");
    }
}