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

    def __init__(self):
        self.children = {}
        self.c_end = 0  # 为单词结尾个数
        self.string = ''  # 单词
        self.fail = None  # 失配位置
        self.last = None  # 后缀链接（suffix link），用来快速跳到一定是某个 words[k] 的最后一个字母的节点（等于 root 则表示没有）

    def insert(self, s: str):
        node = self
        for c in s:
            if c not in node.children:
                node.children[c] = Tire()
                node.children[c].last = self
            node = node.children[c]
        node.c_end += 1
        node.string = s

    def query(self, s) -> bool:
        node = self
        for c in s:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.c_end != 0

    def build_failed(self):
        root = self
        queue = [root]  # root所在层为第0层
        while queue:  # 广度优先遍历
            node = queue.pop(0)
            # 将其孩子逐个加入列队
            for i, child in node.children.items():
                if node == root:
                    child.fail = root  # 第1层的节点的fail总是指向root
                else:
                    p = node.fail  # 第2层以下的节点, 其fail是在另一个分支上
                    while p:
                        # 遍历它的孩子，看它们有没与当前孩子相同字符的节点
                        if i in p.children:
                            child.fail = p.children[i]
                            # 沿着 last 往上走，可以直接跳到一定是某个 words[k] 的最后一个字母的节点（如果跳到 root 表示没有匹配）
                            child.last = child.fail if child.fail.c_end else child.fail.last
                            break
                        p = p.fail
                    if not p:
                        child.fail = root
                        child.last = root
                queue.append(child)

    def match(self, text):
        root, p = self, self
        ret, unique = [], set()
        for i, c in enumerate(text):
            while p != root and c not in p.children:  # type: ignore
                p = p.fail  #  失配指针发挥作用 # type: ignore
            # 如果没有匹配的，从 root 开始重新匹配
            p = p.children[c] if c in p.children else root  # type: ignore
            node: Tire = p
            while node != root:
                #  收集出可以匹配的模式串
                if node.c_end:
                    pos = i - len(node.string) + 1
                    # console.log(`匹配模式串 ${node.pattern}其起始位置在${pos}`)
                    if not node.string in unique:
                        unique.add(node.string)
                        ret.append(node.string)
                node = node.fail  # type: ignore
        return ret


class Solution:

    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        # AC 自动机
        n = len(target)
        LIMIT = 0x3c3c3c3c3c3c3c
        dp = [0] + [LIMIT] * n
        t = Tire()
        cost_dic = defaultdict(lambda: LIMIT)
        for w, c in zip(words, costs):
            t.insert(w)
            cost_dic[w] = min(cost_dic[w], c)
        t.build_failed()
        # print(t.match(target))
        cur = t
        for i, c in enumerate(target):
            while cur != t and c not in cur.children:  # type: ignore
                cur = cur.fail  #  失配指针发挥作用 # type: ignore
            # 如果没有匹配的，从 root 开始重新匹配
            cur = cur.children[c] if c in cur.children else t  # type: ignore
            node: Tire = cur
            while node != t:
                #  收集出可以匹配的模式串
                if node.c_end:
                    dp[i + 1] = min(dp[i + 1], cost_dic[node.string] + dp[i + 1 - len(node.string)])
                node = node.last  # type: ignore

        return dp[-1] if dp[-1] != LIMIT else -1
45000