<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 Vertex:
    def __init__(self, parent=None, ln=0):
        self.output = []         # List of string lengths ending at this vertex
        self.parent = parent     # Reference to the parent vertex (not an index)
        self.link = None         # Suffix link (failure link)
        self.go = {}             # Transitions to child nodes (using dictionaries)
        self.ln = ln             # Length of the prefix

class AhoCorasick:

    def __init__(self, words=[]):
        self.root = Vertex()
        for word in words:
            self.add_string(word)
        self.build_automaton()

    def add_string(self, s):
        node = self.root
        for i, ch in enumerate(s):
            if ch not in node.go:
                node.go[ch] = Vertex(node, i + 1)
            node = node.go[ch]
        node.output.append(len(s))

    def build_automaton(self):
        root = self.root
        queue = deque()
        for node in root.go.values():
            queue.append(node)
            node.link = root

        while queue:
            current_node = queue.popleft()
            for ch, child_node in current_node.go.items():
                queue.append(child_node)
                
                if current_node == self.root:
                    child_node.link = self.root
                else:
                    suffix_node = current_node.link
                    while suffix_node != self.root and ch not in suffix_node.go:
                        suffix_node = suffix_node.link
                    child_node.link = suffix_node.go[ch] if ch in suffix_node.go else self.root
                    child_node.output = child_node.output + child_node.link.output

    def go(self, node, ch):
        if ch not in node.go:
            tmp=node
            while tmp != self.root and ch not in tmp.go:
                tmp = tmp.link
            node.go[ch]=tmp.go[ch] if ch in tmp.go else self.root
        return node.go[ch]

    def iter_matches(self, sentence):
        node = self.root        
        for i, ch in enumerate(sentence):
            node = self.go(node, ch)
            if node.ln > 0:
                yield (i, node.ln)
                
class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        tr=AhoCorasick(words)
        n=len(target)
        dp=[inf]*(n+1)
        dp[0]=0
        for i,ln in tr.iter_matches(target):
            dp[i + 1] = dp[i + 1 - ln] + 1

        return dp[-1] if dp[-1]!=inf else -1
51311