<p>You are given an array of strings <code>words</code> and a string <code>target</code>.</p>

<p>A string <code>x</code> is called <strong>valid</strong> if <code>x</code> is a <span data-keyword="string-prefix">prefix</span> of <strong>any</strong> string in <code>words</code>.</p>

<p>Return the <strong>minimum</strong> number of <strong>valid</strong> strings that can be <em>concatenated</em> to form <code>target</code>. If it is <strong>not</strong> possible to form <code>target</code>, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abc&quot;,&quot;aaaaa&quot;,&quot;bcdef&quot;], target = &quot;aabcdabc&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>The target string can be formed by concatenating:</p>

<ul>
	<li>Prefix of length 2 of <code>words[1]</code>, i.e. <code>&quot;aa&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[2]</code>, i.e. <code>&quot;bcd&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[0]</code>, i.e. <code>&quot;abc&quot;</code>.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abababab&quot;,&quot;ab&quot;], target = &quot;ababaababa&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>The target string can be formed by concatenating:</p>

<ul>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abcdef&quot;], target = &quot;xyz&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 100</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 5 * 10<sup>3</sup></code></li>
	<li>The input is generated such that <code>sum(words[i].length) &lt;= 10<sup>5</sup></code>.</li>
	<li><code>words[i]</code> consists only of lowercase English letters.</li>
	<li><code>1 &lt;= target.length &lt;= 5 * 10<sup>3</sup></code></li>
	<li><code>target</code> consists only of lowercase English letters.</li>
</ul>

# pyre-strict

import bisect
from typing import *
from sortedcontainers import SortedList, SortedDict
from collections import Counter, defaultdict
from math import inf
from math import gcd
from math import factorial
import string
import random
import itertools
from functools import cache
from fractions import Fraction


class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        N = len(target)
        target = "#" + target  # 1-indexed
        bit = [inf] * (N + 10)

        def update(i: int, x: int) -> None:
            assert i >= 1
            while i < len(bit):
                bit[i] = min(bit[i], x)
                i += i & -i

        def query(i: int) -> int:
            assert i >= 1
            res = inf
            while i:
                res = min(res, bit[i])
                i -= i & -i
            return res

        MOD = 10 ** 18 + 3
        BASE = random.randint(2, MOD - 1)
        POWS = [1] * (N + 1)
        word_hashes: set[int] = set()
        for word in words:
            h = 0
            for c in word:
                h = (h * BASE + ord(c) - ord('a') + 1) % MOD
                word_hashes.add(h)

        for i in range(1, N):
            POWS[i] = POWS[i - 1] * BASE % MOD
        target_prefix_hashes = [0] * (N + 1)
        for i in range(1, N + 1):
            target_prefix_hashes[i] = (target_prefix_hashes[i - 1] * BASE + ord(target[i]) - ord('a') + 1) % MOD

        def get_hash(l: int, r: int) -> int:
            return (target_prefix_hashes[r] + MOD - target_prefix_hashes[l - 1] * POWS[r - l + 1] % MOD) % MOD

        # print(word_hashes)
        # print(target_prefix_hashes)
        dp = [inf] * (N + 2)
        dp[N + 1] = 0
        update(N + 1, 0)
        for i in range(N, 0, -1):
            # print(target[i:])
            # print(get_hash(i, i), word_hashes)
            if get_hash(i, i) in word_hashes:
                L = i
                R = N + 1
                while L + 1 < R:
                    mid = (L + R) // 2
                    if get_hash(i, mid) in word_hashes:
                        L = mid
                    else:
                        R = mid
                dp[i] = query(L + 1) + 1
                update(i, dp[i])

        return dp[1] if dp[1] < inf else -1


sol = Solution()
print(sol.minValidStrings(words=["abc", "aaaaa", "bcdef"], target="aabcdabc"))
print(sol.minValidStrings(words=["abababab", "ab"], target="ababaababa"))
print(sol.minValidStrings(words=["abcdef"], target="xyz"))

21931