Rabin-Karp Hash Function + Modular Arithmetic + Prefix Sum + Binary Search + Segment Tree
Intuition\n Describe your first thoughts on how to solve this problem. \n- Let $dp[i]$ be the minimum cost to form the prefix of length $i$ of target.\n- Use Ra
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Let $dp[i]$ be the minimum cost to form the prefix of length $i$ of target.\n- Use Rabin-Karp to hash every prefix of the $words$ and store it in a HashSet.\n- Use prefix sum to hash every prefix of the $target$ string\n- Use Binary search to find the longest substring starting at index $i$ ($target[i..j]$) that has a hash present in the HashSet.\n- Use Segment Tree to update $dp[i..j]$\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nRabin-Karp Hash Function + Modular Arithmetic + Prefix Sum + Binary Search + Segment Tree\n\n# Complexity\n- Time complexity: $O(m*l + n*logn)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(m*l + n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nwhere $m$ is the length of the $words$ array, $l$ is the maximum length of the string in the $words$ array, and $n$ is the length of the $target$ string\n\n# Code\n```rust []\nuse std::collections::HashSet;\n\nconst MOD: i128 = 1000000000000000007;\n\nimpl Solution {\n    pub fn min_valid_strings(words: Vec<String>, target: String) -> i32 {\n        let mut h = HashSet::new();        \n\n        for w in words {\n            let mut s = 0;\n\n            for c in w.chars() {\n                s = (27*s + (c as u8 - b\'a\' + 1) as i128) % MOD;\n                h.insert(s);\n            }\n        }\n\n        let n = target.len();\n        let b = target.as_bytes();\n\n        let mut p = vec![0; n];\n        let mut ht = vec![0; n];\n\n        let mut s = 0;\n\n        for i in 0..n {            \n            s = (27*s + (b[i] - b\'a\' + 1) as i128) % MOD;\n\n            if i == 0 {\n                p[i] = 1;\n            } else {\n                p[i] = (27*p[i-1]) % MOD;\n            }\n\n            ht[i] = s;            \n        }\n\n        let l = Self::search(0, &h, &ht, &p);\n\n        if l == 0 {\n            return -1;\n        }\n\n        if l == n {\n            return 1;\n        }       \n\n        let mut t = vec![0; 2*n + 1];\n\n        for i in 0..n+1 {\n            t[i+n] = i32::MAX;\n        }\n\n        for i in (2..t.len()).step_by(2).rev() {\n            t[(i-1)/2] = t[i].min(t[i-1]);\n        }         \n\n        Self::set(0, 1, n + 1, &mut t);\n        Self::set(l, 2, n + 1, &mut t);\n\n        for i in 1..n {\n            let c = Self::min(i, n, n + 1, &t);\n\n            if c == i32::MAX {\n                return -1;\n            }\n\n            let l = Self::search(i, &h, &ht, &p);\n\n            if i + l == n {\n                Self::set(n, c, n + 1, &mut t);\n            } else {\n                let pc = Self::min(i + l, i + l, n + 1, &t);\n\n                if pc > c + 1 {\n                    Self::set(i + l, c + 1, n + 1, &mut t);\n                }\n            }\n        }\n\n        let c = Self::min(n, n, n + 1, &t);\n\n        if c == i32::MAX {-1} else {c}\n    }  \n\n    pub fn search(i: usize, h: &HashSet<i128>, ht: &Vec<i128>, p: &Vec<i128>) -> usize {\n        let n = ht.len();\n\n        let mut l = 0;\n        let mut r = n - i;\n\n        while l < r {\n            let m = (l + r + 1)/2;\n\n            let mut hc = ht[i+m-1];            \n\n            if i > 0 {\n                hc = (hc + MOD - (ht[i-1]*p[m]) % MOD) % MOD;\n            }                        \n\n            if h.contains(&hc) {\n                l = m;\n            } else {\n                r = m - 1;\n            }\n        }\n\n        l\n    }\n\n    pub fn min(mut i: usize, mut j: usize, n: usize, t: &Vec<i32>) -> i32 {\n        i += n;\n        j += n;\n\n        let mut r = i32::MAX;\n\n        while i <= j {\n            if i % 2 == 1 {\n                r = r.min(t[i-1]);\n                i += 1;\n            } \n            \n            if j % 2 == 0 {\n                r = r.min(t[j-1]);\n                j -= 1;\n            }\n\n            i /= 2;\n            j /= 2;\n        }\n\n        r\n    }    \n\n    pub fn set(mut k: usize, v: i32, n: usize, t: &mut Vec<i32>) {\n        k += n;\n\n        t[k-1] = v;\n\n        k /= 2;\n\n        while k >= 1 {\n            t[k-1] = t[2*k-1].min(t[2*k]);\n\n            k /= 2;\n        }\n    }    \n}\n```
['Math', 'Binary Search', 'Segment Tree', 'Hash Function', 'Prefix Sum', 'Rust']