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

class Solution:
    def minValidStrings_v1(self, words: List[str], target: str) -> int:
        def prefix_function(s: str):
            n = len(s)
            pi = [0] * n
            for i in range(1, n):
                j = pi[i - 1]
                while j > 0 and s[i] != s[j]:
                    j = pi[j - 1]
                if s[i] == s[j]:
                    j += 1
                pi[i] = j
            return pi

        # Greedy match right-to-left, take the largest prefix
        # in words that is also a suffix in target. See KMP.
        n = len(target)
        dp = [0] * n  # dp[i] is the longest prefix that ends at target[i]
        for word in words:
            l = len(word)
            combined = word + "#" + target
            pi = prefix_function(combined)
            for i in range(n):
                dp[i] = max(dp[i], pi[i + l + 1])
        res = 0
        end = n - 1
        while end >= 0:
            if dp[end] == 0:
                break
            end -= dp[end]
            res += 1
        return res if end == -1 else -1

    def minValidStrings_v3b(self, words: List[str], target: str) -> int:
        # Max prefix using prefix tree
        @cache
        def dfs(start):
            if start == n:
                return 0
            start2 = prefixEnd(start)
            res = float("inf")
            while start2 > start:
                res2 = dfs(start2)
                if res2 >= 0:
                    res = min(res, res2 + 1)
                start2 -= 1
            return res if res != float("inf") else -1

        def prefixEnd(p):
            # search
            node = root
            for i in range(p, n):
                ch = target[i]
                if ch not in node:
                    return i
                node = node[ch]
            return n

        n = len(target)
        root = {}
        for word in words:
            # insert
            node = root
            for ch in word:
                if ch not in node:
                    node[ch] = {}
                node = node[ch]
        return dfs(0)

    def minValidStrings(self, words: List[str], target: str) -> int:
        # Max prefix using z-function
        def z_function(s: str):
            n = len(s)
            z = [0] * n
            l, r = 0, 0
            for i in range(1, n):
                if i < r:
                    z[i] = min(r - i, z[i - l])
                while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                    z[i] += 1
                if i + z[i] > r:
                    l, r = i, i + z[i]
            return z

        n = len(target)
        prefixSize = [0] * n
        for word in words:
            l = len(word)
            combined = word + "#" + target
            z = z_function(combined)
            for i in range(n):
                prefixSize[i] = max(prefixSize[i], z[i + l + 1])
        # See problem 45, Jump Game II
        level = 0
        levelEnd = 0
        nextLevelEnd = 0
        for i in range(n):
            nextLevelEnd = max(nextLevelEnd, i + prefixSize[i])
            if nextLevelEnd >= n:
                return level + 1
            if i == levelEnd:
                if nextLevelEnd <= levelEnd:
                    return -1
                levelEnd = nextLevelEnd
                level += 1
        return -1

26148