<p>You are given a string <code>target</code>, an array of strings <code>words</code>, and an integer array <code>costs</code>, both arrays of the same length.</p>

<p>Imagine an empty string <code>s</code>.</p>

<p>You can perform the following operation any number of times (including <strong>zero</strong>):</p>

<ul>
	<li>Choose an index <code>i</code> in the range <code>[0, words.length - 1]</code>.</li>
	<li>Append <code>words[i]</code> to <code>s</code>.</li>
	<li>The cost of operation is <code>costs[i]</code>.</li>
</ul>

<p>Return the <strong>minimum</strong> cost to make <code>s</code> equal to <code>target</code>. If it&#39;s not possible, 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">target = &quot;abcdef&quot;, words = [&quot;abdef&quot;,&quot;abc&quot;,&quot;d&quot;,&quot;def&quot;,&quot;ef&quot;], costs = [100,1,1,10,5]</span></p>

<p><strong>Output:</strong> <span class="example-io">7</span></p>

<p><strong>Explanation:</strong></p>

<p>The minimum cost can be achieved by performing the following operations:</p>

<ul>
	<li>Select index 1 and append <code>&quot;abc&quot;</code> to <code>s</code> at a cost of 1, resulting in <code>s = &quot;abc&quot;</code>.</li>
	<li>Select index 2 and append <code>&quot;d&quot;</code> to <code>s</code> at a cost of 1, resulting in <code>s = &quot;abcd&quot;</code>.</li>
	<li>Select index 4 and append <code>&quot;ef&quot;</code> to <code>s</code> at a cost of 5, resulting in <code>s = &quot;abcdef&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">target = &quot;aaaa&quot;, words = [&quot;z&quot;,&quot;zz&quot;,&quot;zzz&quot;], costs = [1,10,100]</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>

<p><strong>Explanation:</strong></p>

<p>It is impossible to make <code>s</code> equal to <code>target</code>, so we return -1.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length == costs.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words[i].length &lt;= target.length</code></li>
	<li>The total sum of <code>words[i].length</code> is less than or equal to <code>5 * 10<sup>4</sup></code>.</li>
	<li><code>target</code> and <code>words[i]</code> consist only of lowercase English letters.</li>
	<li><code>1 &lt;= costs[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Vertex:
    def __init__(self):
        self.output = defaultdict(lambda:inf)
        self.link = None         # Suffix link (failure link)
        self.go = {}             # Transitions to child nodes (using dictionaries)

class AhoCorasick:

    def __init__(self, words,costs):
        self.root = Vertex()
        for word, cost in zip(words, costs):
            self.add_string(word, cost)
        self.build_automaton()

    def add_string(self, word,cost):
        node = self.root
        for i, ch in enumerate(word):
            if ch not in node.go:
                node.go[ch] = Vertex()
            node = node.go[ch]
        node.output[len(word)] = min(node.output[len(word)],cost)

    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
                    if child_node.link!=self.root:
                        for sz,cost in child_node.link.output.items():
                            child_node.output[sz]=min(child_node.output[sz],cost)
    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)
            
            for sz,cost in node.output.items():
                yield (i, sz, cost)

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        tr = AhoCorasick(words, costs)
        n = len(target)
        dp = [inf] * (n + 1)
        dp[0] = 0

        node = tr.root
        for i,ch in enumerate(target):
            node = tr.go(node, ch)
            for sz,cost in node.output.items():
                dp[i+1] = min(dp[i+1], dp[i - (sz-1)] + cost)

        return dp[n] if dp[n] != inf else -1
63400