<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 SegNode:
    def __init__(self, l, r, val=0, left=None, right=None, lazy=inf):
        self.l, self.r, self.val = l, r, val
        self.left, self.right = left, right
        self.lazy = lazy

class SegTree:
    def __init__(self, vals):
        def _build(l, r):
            if l == r:
                return SegNode(l, r, vals[l])
            m = (l + r) // 2
            left, right = _build(l, m), _build(m + 1, r)
            return SegNode(l, r, min(left.val, right.val), left, right)

        self.root = _build(0, len(vals) - 1)

    def update(self, l, r, val, node):
        if node.lazy != inf:
            self.propagate(node)
        if node.r < l or r < node.l:
            return
        if l <= node.l and r >= node.r:
            node.val = min(node.val, val)
            if node.l != node.r:
                node.left.lazy = min(node.left.lazy, val)
                node.right.lazy = min(node.right.lazy, val)
            return
        self.update(l, r, val, node.left)
        self.update(l, r, val, node.right)
        node.val = min(node.left.val, node.right.val)

    def propagate(self, node):
        node.val = min(node.val, node.lazy)
        if node.l != node.r:
            node.left.lazy = min(node.left.lazy, node.lazy)
            node.right.lazy = min(node.left.lazy, node.lazy)
        node.lazy = inf

    def query(self, l, r, node):
        if node.lazy != inf:
            self.propagate(node)
        if node.r < l or r < node.l:
            return inf
        if l <= node.l and r >= node.r:
            return node.val
        a = self.query(l, r, node.left)
        b = self.query(l, r, node.right)
        return min(a, b)

class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        def z_function(S):
            n = len(S)
            Z = [0] * n
            left, right = 0, 0
            for i in range(1, n):
                if i <= right:
                    Z[i] = min(right - i + 1, Z[i - left])
                while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:
                    Z[i] += 1
                if i + Z[i] - 1 > right:
                    left, right = i, i + Z[i] - 1
            Z[0] = n
            return Z

        N = len(target)
        INF = 1 << 50 
        e = [0] * N
        for word in words:
            z_values = z_function(word + "#" + target)
            for index in range(N):
                x = z_values[len(word) + 1 + index]
                if x != 0:
                    e[index] = max(e[index], x)

        k = [inf] * (len(target) + 1)
        k[0] = 0
        tree = SegTree(k)
        for i in range(1, len(k)):
            s = e[i - 1]
            p = tree.query(i - 1, i - 1, tree.root)
            if p == inf:
                break
            tree.update(i, i + s - 1, p + 1, tree.root)

        ans = tree.query(i, i, tree.root)
        return ans if ans != inf else -1

18999