Distinct echo substrings

String Trie Rolling Hash Hash Function

53.0% acceptance

Feb 25, 2026

337

208

Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself (i.e. it can be written as a + a where a is some string).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn distinct_echo_substrings(text: String) -> i32 {
    let b = text.as_bytes();
    let n = b.len();
    const B1: u64 = 31;
    const M1: u64 = 1_000_000_007;
    const B2: u64 = 37;
    const M2: u64 = 998_244_353;

    let mut pw1 = vec![1u64; n + 1];
    let mut pw2 = vec![1u64; n + 1];
    let mut h1 = vec![0u64; n + 1];
    let mut h2 = vec![0u64; n + 1];
    for i in 0..n {
      pw1[i+1] = pw1[i] * B1 % M1;
      pw2[i+1] = pw2[i] * B2 % M2;
      h1[i+1] = (h1[i] * B1 + (b[i] - b'a' + 1) as u64) % M1;
      h2[i+1] = (h2[i] * B2 + (b[i] - b'a' + 1) as u64) % M2;
    }

    let get = |h: &[u64], pw: &[u64], m: u64, l: usize, r: usize| -> u64 {
      (h[r] + m * m - h[l] * pw[r - l] % m) % m
    };

    let mut seen = std::collections::HashSet::new();
    for k in 1..=n/2 {
      for i in 0..=n - 2*k {
        let a1 = get(&h1, &pw1, M1, i, i+k);
        let b1_val = get(&h1, &pw1, M1, i+k, i+2*k);
        if a1 == b1_val {
          let a2 = get(&h2, &pw2, M2, i, i+k);
          let b2 = get(&h2, &pw2, M2, i+k, i+2*k);
          if a2 == b2 {
            seen.insert((get(&h1, &pw1, M1, i, i+2*k), 2*k));
          }
        }
      }
    }
    seen.len() as i32
  }
}