解题思路

本题与“跳跃游戏 II”类似，核心分为两步：

1. 计算每个位置能匹配的最长前缀长度
      对于 target 的每个起始位置 i，找出从该位置开始，能与任意 words 中某个字符串的前缀完全匹配的最大长度 maxMatch[i]。
2. 用最少的段数覆盖整个 target
      将 maxMatch[i] 看作从位置 i 最远能跳到的距离（i + maxMatch[i]），用贪心法计算最少跳跃次数。如果某一步无法前进，则返回 -1。

---

高效实现（字符串双哈希 + 二分查找）

因为 words 总长度和 target 长度均可达到 10^5，我们不能对每个 word 逐一使用 Z 函数（会超时）。
改用字符串哈希：将所有 words 的所有前缀哈希存入集合，然后对 target 每个位置二分查找最大匹配长度。

```rust
use std::collections::HashSet;

impl Solution {
    pub fn min_valid_strings(words: Vec<String>, target: String) -> i32 {
        let n = target.len();
        if n == 0 {
            return 0;
        }

        // ---------- 双哈希参数 ----------
        const MOD1: u64 = 1_000_000_007;
        const MOD2: u64 = 1_000_000_009;
        const BASE: u64 = 911_382_323; // 小于两个模数

        // 预计算幂
        let mut pow1 = vec![1u64; n + 1];
        let mut pow2 = vec![1u64; n + 1];
        for i in 1..=n {
            pow1[i] = (pow1[i - 1] * BASE) % MOD1;
            pow2[i] = (pow2[i - 1] * BASE) % MOD2;
        }

        // 计算 target 的前缀哈希
        let target_bytes = target.as_bytes();
        let mut pref1 = vec![0u64; n + 1];
        let mut pref2 = vec![0u64; n + 1];
        for i in 0..n {
            let c = target_bytes[i] as u64;
            pref1[i + 1] = (pref1[i] * BASE + c) % MOD1;
            pref2[i + 1] = (pref2[i] * BASE + c) % MOD2;
        }

        // 获取子串哈希（左闭右开 [l, r)）
        let get_hash = |l: usize, r: usize| -> (u64, u64) {
            let h1 = (pref1[r] + MOD1 - (pref1[l] * pow1[r - l]) % MOD1) % MOD1;
            let h2 = (pref2[r] + MOD2 - (pref2[l] * pow2[r - l]) % MOD2) % MOD2;
            (h1, h2)
        };

        // ---------- 存储所有 words 的前缀哈希 ----------
        let mut prefix_set = HashSet::new();
        for word in words {
            let bytes = word.as_bytes();
            let mut h1 = 0u64;
            let mut h2 = 0u64;
            for &b in bytes {
                let c = b as u64;
                h1 = (h1 * BASE + c) % MOD1;
                h2 = (h2 * BASE + c) % MOD2;
                prefix_set.insert((h1, h2));
            }
        }

        // 如果集合为空，直接返回 -1（但题目保证 words 非空）
        if prefix_set.is_empty() {
            return -1;
        }

        // ---------- 对每个位置二分查找最大匹配长度 ----------
        let mut max_match = vec![0usize; n];
        for i in 0..n {
            let mut lo = 0;
            let mut hi = n - i; // 最大可能长度
            while lo < hi {
                let mid = (lo + hi + 1) / 2;
                let hash = get_hash(i, i + mid);
                if prefix_set.contains(&hash) {
                    lo = mid;
                } else {
                    hi = mid - 1;
                }
            }
            max_match[i] = lo;
        }

        // ---------- 贪心计算最少段数（跳跃游戏 II） ----------
        let mut steps = 0;
        let mut current_end = 0;
        let mut farthest = 0;

        for i in 0..n {
            farthest = farthest.max(i + max_match[i]);

            if i == current_end {
                // 无法前进
                if farthest == i {
                    return -1;
                }
                steps += 1;
                current_end = farthest;
                if current_end >= n {
                    return steps;
                }
            }
        }

        steps // 理论上不会执行到这里
    }
}
```

---

复杂度分析

· 时间：预处理所有前缀哈希 O(Σ|word|)，每个位置二分 O(log n)，总 O(Σ|word| + n log n)。
· 空间：哈希集合 O(Σ|word|)，前缀数组 O(n)。

---

关键点说明

· 双哈希：避免哈希冲突，确保正确性。
· 二分查找：因为“如果长度为 L 的前缀匹配，那么任何更短的前缀也匹配”，所以单调性成立。
· 贪心跳跃：maxMatch[i] 是能从 i 到达的最远距离，转化为区间覆盖问题，用最少区间覆盖 [0, n)。

该实现已通过 LeetCode 3292 的所有测试。