<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>

class FenwickTree:
    def __init__(self, n: int = 0):
        self.data = [float('inf')] * n

    def set(self, p, x):
        while p < len(self.data):
            self.data[p] = min(self.data[p], x)
            p = p | (p + 1)

    def min(self, r):
        res = float('inf')
        while r >= 0:
            res = min(res, self.data[r])
            r = (r & (r+1)) - 1
        return res

class SHash:
    def __init__(self, input_string: str):
        self.input_string = input_string
        self.prime = 31
        # self.od1 = 10**9 + 7
        self.mod = 19175002942688032928599
        self.precompute_hashes()
        
    def precompute_hashes(self):
        n = len(self.input_string)
        self.hash = [0] * (n + 1)
        self.pow = [1] * (n + 1)
        
        for i in range(n):
            self.hash[i + 1] = (self.hash[i] * self.prime + ord(self.input_string[i])) % self.mod
            self.pow[i + 1] = (self.pow[i] * self.prime) % self.mod
            
    def get_hash(self, start: int, end: int):
        hash_val = (self.hash[end + 1] - self.hash[start] * self.pow[end - start + 1]) % self.mod
        
        return hash_val
        # return (hash_val1, hash_val2)

class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        # hashes
        prefixes = set()
        for w in words:
            shash = SHash(w)
            m = len(w)
            for l in range(1, m + 1):
                h = shash.get_hash(0, l - 1)
                prefixes.add(h)

        n = len(target)
        thash = SHash(target)
        fw = FenwickTree(n)
        dp = [float('inf')] * n
        # dp[i] is the minimum score of target[i:]
        for i in range(n-1, -1, -1):
            l = i
            r = n-1
            while l < r:
                m = (l + r + 1) // 2
                # if target[i:m+1] in prefixes:
                if thash.get_hash(i, m) in prefixes:
                    l = m
                else:
                    r = m - 1

            if l == i and ord(target[i]) not in prefixes:
            #if l == i and (ord(target[i]), ord(target[i])) not in prefixes:
                dp[i] = float('inf')
            elif l == n-1:
                dp[i] = 1
            else:
                dp[i] = 1 + fw.min(l+1)
            fw.set(i, dp[i])

        return dp[0] if dp[0] != float('inf') else -1

22909