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

from collections import deque

class AhoCorasickNode:
    def __init__(self, depth=0):
        # Children nodes: character -> AhoCorasickNode
        self.children = {}
        # Failure link
        self.fail = None
        # Output: list of patterns ending at this node
        self.output = []
        # Depth of the node in the trie (length of the prefix)
        self.depth = depth
        # Optional: To reconstruct the prefix
        self.parent = None
        self.char = None

class AhoCorasickAutomaton:
    def __init__(self, keywords):
        """
        Initialize the Aho-Corasick automaton with a list of keywords.
        It will match all prefixes of each keyword efficiently.
        """
        self.root = AhoCorasickNode()
        self.build_trie(keywords)
        self.build_failure_links()

    def build_trie(self, keywords):
        """
        Build the trie structure from the list of keywords.
        Only full keywords are inserted; prefixes are handled implicitly.
        """
        for keyword in keywords:
            node = self.root
            for char in keyword:
                if char not in node.children:
                    new_node = AhoCorasickNode(depth=node.depth + 1)
                    new_node.parent = node
                    new_node.char = char
                    node.children[char] = new_node
                node = node.children[char]
            node.output.append(len(keyword))

    def build_failure_links(self):
        """
        Build failure links using BFS traversal.
        """
        queue = deque()
        # Initialize the queue with root's children
        for child_char, child_node in self.root.children.items():
            child_node.fail = self.root
            queue.append(child_node)

        while queue:
            current_node = queue.popleft()
            for char, child_node in current_node.children.items():
                # Set the failure link for child_node
                fail_node = current_node.fail
                while fail_node is not None and char not in fail_node.children:
                    fail_node = fail_node.fail
                child_node.fail = fail_node.children[char] if fail_node and char in fail_node.children else self.root
                # Merge output from failure link
                child_node.output += child_node.fail.output
                # Add child to the queue to process its children
                queue.append(child_node)


    def search_prefixes(self, text):
        """
        Search for all prefixes of the keywords in the given text.
        Returns a list of tuples (start_index, end_index).
        """
        node = self.root
        full_matches = []
        max_partial_results = [-1 for _ in text]

        prefix_length = 0  # Length of the current prefix

        for index, char in enumerate(text):
            while node is not None and char not in node.children:
                node = node.fail
                # Update prefix_length when following failure links
                if node:
                    prefix_length = node.depth
                else:
                    prefix_length = 0  # Reset to 0 when failing to root

            if node:
                node = node.children[char]
                prefix_length = node.depth  # Update prefix length to node's depth

                # Collect matched patterns (full keywords) at this node
                for len_keyword in node.output:
                    end_index = index
                    start_index = end_index - len_keyword + 1
                    full_matches.append((start_index, end_index))
                
                # Collect the maximum prefix indices
                start_idx = index - prefix_length + 1
                end_idx = index
                max_partial_results[start_idx] = end_idx + 1

            else:
                node = self.root  # Restart from root
                prefix_length = 0  # Reset prefix length

        return full_matches, max_partial_results


# Example usage:
if __name__ == "__main__":
    keywords = ["abc","aaaaa","bcdef"]
    text = "aabcdabc"

    automaton = AhoCorasickAutomaton(keywords)
    full_matches, max_partial_results = automaton.search_prefixes(text)

    # To avoid duplicate matches, especially for shared prefixes,
    # you might want to process or filter the results accordingly.
    # For demonstration, we'll print all matches.
    
    # Remove duplicates if necessary
    # unique_matches = set(full_matches)
    # sorted_matches = sorted(unique_matches, key=lambda x: (x[0], x[1]))

    # for start, end in sorted_matches:
    #     print(f"Prefix '{text[start:end+1]}' found at indices {start} to {end}")
    # print(max_partial_results)




class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        
        automaton = AhoCorasickAutomaton(words)
        full_matches, max_partial_results = automaton.search_prefixes(target)

        jumps = 0         # Number of jumps made
        current_end = 0   # The end of the range that we can reach with current number of jumps
        farthest = 0      # The farthest we can reach with current + 1 jumps

        n = len(target)
        for i, nex in enumerate(max_partial_results):
            farthest = max(farthest, nex)

            if i == current_end:
                jumps += 1
                current_end = farthest
            
            if i > current_end:
                return -1

        if current_end == n:
            return jumps
        return -1

54666