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

from typing import List, Optional

class Node:
    def __init__(self, cost: Optional[int] = None):
        self.children = {}
        self.cost = cost

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:

        def build_kmp_prefix() -> List[int]:
            w = [0] * len(target)
            k, i = 0, 1
            while i < len(target):
                if target[i] == target[k]:
                    k += 1
                    w[i] = k
                    i += 1
                else:
                    if k != 0:
                        k = w[k - 1]
                    else:
                        i += 1
            return w

        def find(prefix: List[int], w: str) -> List[List[int]]:
            result = []
            m, n = len(target), len(w)
            i, k = 0, 0
            while i < m:
                if target[i] == w[k]:
                    i += 1
                    k += 1
                if k == n:
                    # Found a match
                    result.append([i - k, i])
                    k = prefix[k - 1]
                elif i < m and target[i] != w[k]:
                    if k != 0:
                        k = prefix[k - 1]
                    else:
                        i += 1
            return result

        target_prefix = build_kmp_prefix()

        root = Node()
        for j, x in enumerate(words):
            if len(x) < 320:
                p = root
                for i in range(len(x)):
                    if x[i] in p.children:
                        p = p.children[x[i]]
                    else:
                        t = Node()
                        p.children[x[i]] = t
                        p = t
                    if i == len(x) - 1:
                        p.cost = min(costs[j], p.cost) if p.cost is not None else costs[j]

        dm = {}
        for i, word in enumerate(words):
            if len(word) >= 320:
                q = find(target_prefix, word)
                for b, e in q:
                    qm = dm.setdefault(e, {})
                    if b in qm:
                        qm[b] = min(qm[b], costs[i])
                    else:
                        qm[b] = costs[i]

        d = [[root, 0]]
        dp = [-1 for _ in range(len(target) + 1)]
        dp[0] = 0
        for i, x in enumerate(target):
            q = []
            t = None
            for p, cost in d:
                if x in p.children:
                    w = p.children[x]
                    if w.cost is not None:
                        t = cost + w.cost if t is None else min(t, cost + w.cost)
                    q.append([w, cost])
            qm = dm.get(i + 1, {})
            for b in qm:
                if dp[b] >= 0:
                    t = dp[b] + qm[b] if t is None else min(t, dp[b] + qm[b])

            if t is not None:
                dp[i + 1] = t
                q.append([root, t])
            d = q

        return dp[len(target)]
53300