Suffix Array em Rust

/// Constroi o Suffix Array usando ordenacao por rank em O(n * log^2 n).
/// Cada iteracao dobra o comprimento dos prefixos comparados.
fn construir_suffix_array(texto: &str) -> Vec<usize> {
    let bytes = texto.as_bytes();
    let n = bytes.len();

    if n == 0 {
        return Vec::new();
    }

    // Inicializa: rank de cada sufixo = valor do primeiro caractere
    let mut sa: Vec<usize> = (0..n).collect();
    let mut rank: Vec<i64> = bytes.iter().map(|&b| b as i64).collect();
    let mut nova_rank = vec![0i64; n];
    let mut k = 1; // comprimento do prefixo atual

    while k < n {
        // Ordena pelo par (rank[i], rank[i+k])
        let rank_ref = &rank;
        sa.sort_by(|&a, &b| {
            let ra = (rank_ref[a], if a + k < n { rank_ref[a + k] } else { -1 });
            let rb = (rank_ref[b], if b + k < n { rank_ref[b + k] } else { -1 });
            ra.cmp(&rb)
        });

        // Recalcula os ranks
        nova_rank[sa[0]] = 0;
        for i in 1..n {
            let anterior = (
                rank[sa[i - 1]],
                if sa[i - 1] + k < n { rank[sa[i - 1] + k] } else { -1 },
            );
            let atual = (
                rank[sa[i]],
                if sa[i] + k < n { rank[sa[i] + k] } else { -1 },
            );
            nova_rank[sa[i]] = nova_rank[sa[i - 1]] + if atual != anterior { 1 } else { 0 };
        }

        rank.copy_from_slice(&nova_rank);

        // Se todos os ranks sao unicos, ja terminamos
        if rank[sa[n - 1]] as usize == n - 1 {
            break;
        }

        k *= 2;
    }

    sa
}

/// Constroi o array LCP usando o algoritmo de Kasai em O(n).
fn construir_lcp(texto: &str, sa: &[usize]) -> Vec<usize> {
    let bytes = texto.as_bytes();
    let n = bytes.len();

    if n == 0 {
        return Vec::new();
    }

    // rank[i] = posicao do sufixo i no Suffix Array
    let mut rank = vec![0usize; n];
    for (i, &s) in sa.iter().enumerate() {
        rank[s] = i;
    }

    let mut lcp = vec![0usize; n];
    let mut h: usize = 0;

    for i in 0..n {
        if rank[i] > 0 {
            let j = sa[rank[i] - 1]; // sufixo anterior no SA

            // Compara caracteres a partir da posicao h
            while i + h < n && j + h < n && bytes[i + h] == bytes[j + h] {
                h += 1;
            }

            lcp[rank[i]] = h;

            if h > 0 {
                h -= 1; // propriedade de Kasai: h diminui no maximo 1
            }
        } else {
            h = 0;
        }
    }

    lcp
}

/// Busca uma substring no texto usando o Suffix Array e busca binaria.
/// Retorna todas as posicoes onde a substring aparece.
fn buscar_substring(texto: &str, sa: &[usize], padrao: &str) -> Vec<usize> {
    let texto_bytes = texto.as_bytes();
    let padrao_bytes = padrao.as_bytes();
    let n = texto_bytes.len();
    let m = padrao_bytes.len();

    if m == 0 || n == 0 {
        return Vec::new();
    }

    // Busca binaria: encontra o limite inferior
    let mut low = 0usize;
    let mut high = n;

    while low < high {
        let mid = low + (high - low) / 2;
        let sufixo = &texto_bytes[sa[mid]..];
        let cmp_len = m.min(sufixo.len());
        if sufixo[..cmp_len] < padrao_bytes[..cmp_len]
            || (cmp_len < m && sufixo.len() < m)
        {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    let inicio = low;

    // Busca binaria: encontra o limite superior
    high = n;
    while low < high {
        let mid = low + (high - low) / 2;
        let sufixo = &texto_bytes[sa[mid]..];
        let cmp_len = m.min(sufixo.len());
        if sufixo[..cmp_len] <= padrao_bytes[..cmp_len]
            && (cmp_len >= m || sufixo.len() >= m)
        {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    // Coleta todas as posicoes no intervalo [inicio, low)
    let mut posicoes: Vec<usize> = (inicio..low)
        .filter(|&i| {
            let sufixo = &texto_bytes[sa[i]..];
            sufixo.len() >= m && sufixo[..m] == padrao_bytes[..]
        })
        .map(|i| sa[i])
        .collect();

    posicoes.sort();
    posicoes
}

/// Encontra a maior substring que se repete no texto.
fn maior_substring_repetida(texto: &str, sa: &[usize], lcp: &[usize]) -> Option<String> {
    if lcp.is_empty() {
        return None;
    }

    let mut max_lcp = 0;
    let mut max_pos = 0;

    for (i, &valor) in lcp.iter().enumerate() {
        if valor > max_lcp {
            max_lcp = valor;
            max_pos = sa[i];
        }
    }

    if max_lcp == 0 {
        None
    } else {
        Some(texto[max_pos..max_pos + max_lcp].to_string())
    }
}

fn main() {
    let texto = "banana";

    println!("Texto: \"{}\"", texto);
    println!();

    // Constroi Suffix Array
    let sa = construir_suffix_array(texto);
    println!("Suffix Array:");
    println!("  SA  Sufixo");
    for (i, &pos) in sa.iter().enumerate() {
        println!("  [{}]  \"{}\"", pos, &texto[pos..]);
    }
    println!();

    // Constroi LCP
    let lcp = construir_lcp(texto, &sa);
    println!("Array LCP:");
    println!("  SA  LCP  Sufixo");
    for (i, &pos) in sa.iter().enumerate() {
        println!("  [{}]  {}    \"{}\"", pos, lcp[i], &texto[pos..]);
    }
    println!();

    // Busca de substring
    let padrao = "ana";
    let posicoes = buscar_substring(texto, &sa, padrao);
    println!("Busca por \"{}\": posicoes {:?}", padrao, posicoes);
    println!();

    // Maior substring repetida
    match maior_substring_repetida(texto, &sa, &lcp) {
        Some(sub) => println!("Maior substring repetida: \"{}\"", sub),
        None => println!("Nenhuma substring repetida encontrada."),
    }
}

/// Conta o numero total de substrings distintas.
/// Total de substrings = n*(n+1)/2 - soma(LCP)
fn contar_substrings_distintas(texto: &str) -> usize {
    let n = texto.len();
    if n == 0 {
        return 0;
    }

    let sa = construir_suffix_array(texto);
    let lcp = construir_lcp(texto, &sa);

    let total_substrings = n * (n + 1) / 2;
    let soma_lcp: usize = lcp.iter().sum();

    total_substrings - soma_lcp
}

fn main() {
    let texto = "banana";
    println!(
        "Substrings distintas de \"{}\": {}",
        texto,
        contar_substrings_distintas(texto)
    );
    // Resposta: 15 (a, an, ana, anan, anana, b, ba, ban, bana, banan, banana, n, na, nan, nana)
}

/// Encontra a maior substring comum entre dois textos.
/// Tecnica: concatena as strings com separador e usa LCP.
fn maior_substring_comum(texto1: &str, texto2: &str) -> String {
    let n1 = texto1.len();
    // Usa '#' como separador (deve nao aparecer nos textos)
    let combinado = format!("{}#{}", texto1, texto2);

    let sa = construir_suffix_array(&combinado);
    let lcp = construir_lcp(&combinado, &sa);

    let mut max_len = 0;
    let mut max_pos = 0;

    for i in 1..sa.len() {
        // Verifica se os sufixos adjacentes pertencem a strings diferentes
        let pertence_1_atual = sa[i] < n1;
        let pertence_1_anterior = sa[i - 1] < n1;

        // Um deve estar em texto1 e outro em texto2
        if pertence_1_atual != pertence_1_anterior && lcp[i] > max_len {
            max_len = lcp[i];
            max_pos = sa[i];
        }
    }

    if max_len == 0 {
        String::new()
    } else {
        combinado[max_pos..max_pos + max_len].to_string()
    }
}

fn main() {
    let t1 = "abcdefg";
    let t2 = "xyzdefabc";
    let lcs = maior_substring_comum(t1, t2);
    println!(
        "Maior substring comum entre \"{}\" e \"{}\": \"{}\"",
        t1, t2, lcs
    );
}

/// Encontra todas as substrings que aparecem pelo menos `min_vezes` vezes.
fn substrings_frequentes(texto: &str, min_vezes: usize) -> Vec<(String, usize)> {
    let sa = construir_suffix_array(texto);
    let lcp = construir_lcp(texto, &sa);
    let n = sa.len();

    let mut resultados: Vec<(String, usize)> = Vec::new();
    let mut i = 1;

    while i < n {
        if lcp[i] > 0 {
            // Encontra o maior bloco onde LCP >= lcp[i]
            let comprimento = lcp[i];
            let mut contagem = 2; // os dois sufixos adjacentes
            let mut j = i + 1;
            while j < n && lcp[j] >= comprimento {
                contagem += 1;
                j += 1;
            }

            if contagem >= min_vezes {
                let substring = texto[sa[i]..sa[i] + comprimento].to_string();
                resultados.push((substring, contagem));
            }
        }
        i += 1;
    }

    // Remove duplicatas mantendo a contagem maxima
    resultados.sort_by(|a, b| b.0.len().cmp(&a.0.len()));
    resultados.dedup_by(|a, b| a.0 == b.0);
    resultados
}

/// Indice de busca full-text usando Suffix Array.
struct IndiceBusca {
    texto: String,
    sa: Vec<usize>,
    // Mapeia posicao no texto concatenado -> (indice do doc, posicao no doc)
    mapa_docs: Vec<(usize, usize)>,
    nomes_docs: Vec<String>,
}

impl IndiceBusca {
    fn construir(documentos: &[(&str, &str)]) -> Self {
        let mut texto = String::new();
        let mut mapa_docs = Vec::new();
        let mut nomes_docs = Vec::new();

        for (idx, (nome, conteudo)) in documentos.iter().enumerate() {
            let inicio = texto.len();
            texto.push_str(conteudo);
            texto.push('\0'); // separador entre documentos

            for pos in 0..conteudo.len() {
                // Mapeia posicao global -> (doc_idx, posicao_local)
                while mapa_docs.len() <= inicio + pos {
                    mapa_docs.push((idx, pos));
                }
            }
            // Posicao do separador
            mapa_docs.push((idx, conteudo.len()));

            nomes_docs.push(nome.to_string());
        }

        let sa = construir_suffix_array(&texto);

        IndiceBusca {
            texto,
            sa,
            mapa_docs,
            nomes_docs,
        }
    }

    fn buscar(&self, consulta: &str) -> Vec<(String, usize)> {
        let posicoes = buscar_substring(&self.texto, &self.sa, consulta);
        let mut resultados = Vec::new();

        for pos in posicoes {
            if pos < self.mapa_docs.len() {
                let (doc_idx, pos_local) = self.mapa_docs[pos];
                resultados.push((self.nomes_docs[doc_idx].clone(), pos_local));
            }
        }

        resultados
    }
}

fn main() {
    let docs = vec![
        ("manual.txt", "rust e uma linguagem de programacao segura e rapida"),
        ("artigo.txt", "a linguagem rust garante seguranca de memoria"),
        ("tutorial.txt", "aprenda rust do zero com exemplos praticos"),
    ];

    let indice = IndiceBusca::construir(&docs);
    let consulta = "rust";
    let resultados = indice.buscar(consulta);

    println!("Busca por \"{}\":", consulta);
    for (doc, pos) in &resultados {
        println!("  Encontrado em \"{}\" na posicao {}", doc, pos);
    }
}