<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>4</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>4</sup></code></li>
	<li><code>target</code> consists only of lowercase English letters.</li>
</ul>

from collections import defaultdict

class SHash:
    def __init__(self, input_string: str):
        self.input_string = input_string
        self.prime1 = 31
        self.prime2 = 37
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.precompute_hashes()
        
    def precompute_hashes(self):
        n = len(self.input_string)
        self.hash1 = [0] * (n + 1)
        self.hash2 = [0] * (n + 1)
        self.pow1 = [1] * (n + 1)
        self.pow2 = [1] * (n + 1)
        
        for i in range(n):
            self.hash1[i + 1] = (self.hash1[i] * self.prime1 + ord(self.input_string[i])) % self.mod1
            self.hash2[i + 1] = (self.hash2[i] * self.prime2 + ord(self.input_string[i])) % self.mod2
            self.pow1[i + 1] = (self.pow1[i] * self.prime1) % self.mod1
            self.pow2[i + 1] = (self.pow2[i] * self.prime2) % self.mod2
            
    def hash(self, start: int, end: int):
        hash_val1 = (self.hash1[end + 1] - self.hash1[start] * self.pow1[end - start + 1]) % self.mod1
        hash_val2 = (self.hash2[end + 1] - self.hash2[start] * self.pow2[end - start + 1]) % self.mod2
        
        return (hash_val1, hash_val2)
    
class SegmentTree:
    def __init__(self, data, default=float('inf'), func=min):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        n = len(target)
        dp = SegmentTree([float('inf')] * (n + 1))
        dp[n] = 0
        groups = defaultdict(set)
        for w in words:
            shash = SHash(w)
            m = len(w)
            for l in range(1, m + 1):
                groups[l].add(shash.hash(0, l - 1))
        shash = SHash(target)
        for i in range(n - 1, -1, -1):
            beg = 1
            end = n - i
            while beg <= end:
                mid = (beg + end) // 2
                if shash.hash(i, i + mid - 1) in groups[mid]:
                    beg = mid + 1
                else:
                    end = mid - 1
            if beg - 1 > 0:
                dp[i] = min(dp[i], 1 + dp.query(i + 1, i + beg))
        if dp[0] == float('inf'):
            return -1
        return dp[0]
56343