1044. Longest Duplicate Substring

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is "".

Example 1:

Input: s = "banana"
Output: "ana"

Example 2:

Input: s = "abcd"
Output: ""

Constraints:

• 2 <= s.length <= 3 * 104
• s consists of lowercase English letters.

1044. Longest Duplicate Substring
struct Solution;

use std::collections::HashMap;

const MOD: u64 = 1_000_000_007;
const P: u64 = 26;

impl Solution {
fn longest_dup_substring(s: String) -> String {
let mut lo = 0;
let mut hi = s.len();
let mut res = "".to_string();
let s: Vec<char> = s.chars().collect();
let n = s.len();
while lo < hi {
let mid = (lo + hi + 1) / 2;
if let Some(s) = Self::exist(mid, &s, n) {
res = s;
lo = mid;
} else {
hi = mid - 1;
}
}
res
}

fn exist(size: usize, s: &[char], n: usize) -> Option<String> {
let mut pos: HashMap<u64, usize> = HashMap::new();
let mut hash: u64 = 0;
let mut pn: u64 = 1;
for i in 0..size {
hash *= P;
hash += (s[i] as u8 - b'a') as u64;
hash %= MOD;
pn *= P;
pn %= MOD;
}
pos.insert(hash, size);
for i in size..n {
hash *= P;
hash += (s[i] as u8 - b'a') as u64;
hash += MOD;
hash -= (pn * (s[i - size] as u8 - b'a') as u64) % MOD;
hash %= MOD;
if let Some(end) = pos.insert(hash, i + 1) {
if s[end - size..end] == s[i + 1 - size..=i] {
return Some(s[i + 1 - size..=i].iter().copied().collect::<String>());
}
}
}
None
}
}

#[test]
fn test() {
let s = "banana".to_string();
let res = "ana".to_string();
assert_eq!(Solution::longest_dup_substring(s), res);
let s = "abcd".to_string();
let res = "".to_string();
assert_eq!(Solution::longest_dup_substring(s), res);