<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 Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        pattern_tb = []
        for pattern in words:
            m = len(pattern)
            lps = [0] * m
            length = 0  # 长度 of the previous longest prefix suffix
            i = 1

            # 构建部分匹配表
            while i < m:
                if pattern[i] == pattern[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1
            pattern_tb.append(lps)

        n = len(target)
        dp = [-1] * n
        for i, pattern in enumerate(words):
            lps = pattern_tb[i]
            m = len(pattern)
            i, j = 0, 0
            start = n
            while i < n:
                if pattern[j] == target[i]:
                    start = min(start, i)
                    i += 1
                    j += 1

                if j == m:
                    # 找到一个匹配
                    dp[start] = max(dp[start], i)
                    j = lps[j - 1]
                    if j > 0:
                        start = i - j
                    else:
                        start = n
                elif i < n and pattern[j] != target[i]:
                    # 发生不匹配
                    if j != 0:
                        j = lps[j - 1]
                        if start < n:
                            dp[start] = max(dp[start], i)
                            if j > 0:
                                start = i - j
                            else:
                                start = n
                    else:
                        i += 1
            if start < n:
                dp[start] = max(dp[start], i)

        queue = deque([0])
        res = 0
        for i in range(n):
            if dp[i] > queue[-1] and len(queue) <= 2:
                if len(queue) > 1:
                    queue.pop()
                queue.append(dp[i])
            if i >= queue[0]:
                res += 1
                queue.popleft()
            if not queue:
                return -1
        return res

20465