<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 TrieNode:
    def __init__(self, c, is_word, word_index):
        self.c = c
        self.is_word = is_word
        self.word_index = word_index
        self.children = {}
        self.parent = None
        self.suffix_link_with_transition_letter = {}
        self.suffix_link = None
        self.terminal_link = None
        self.terminal_link_with_transition_letter = {}
    
    def insert(self, word, word_index, costs):
        current_node = self
        for i in range(len(word)):
            c = word[i]
            if c in current_node.children:
                if i == len(word) - 1:
                    if not current_node.children[c].is_word or (costs[current_node.children[c].word_index] > costs[word_index]):
                        current_node.children[c].is_word = True
                        current_node.children[c].word_index = word_index
                current_node = current_node.children[c]
            else:
                is_word = i == len(word) - 1
                current_node.children[c] = TrieNode(c, is_word, word_index if is_word else -1)
                current_node.children[c].parent = current_node
                current_node = current_node.children[c]
    
    def get_suffix_link(self):
        if self.parent is None:
            self.suffix_link = self
            return self.suffix_link
        if self.parent.parent is None:
            self.suffix_link = self.parent
            return self.suffix_link
        if self.suffix_link is not None:
            return self.suffix_link
        
        suffix_link_with_transition_letter = self.parent.get_suffix_link().get_suffix_link_with_transition_letter(self.c)
        if self.c not in suffix_link_with_transition_letter.children:
            self.suffix_link = suffix_link_with_transition_letter
        else:
            self.suffix_link = suffix_link_with_transition_letter.children[self.c]
        return self.suffix_link

    def get_suffix_link_with_transition_letter(self, c):
        if self.parent is None:
            self.suffix_link_with_transition_letter[c] = self
            return self
        if c in self.suffix_link_with_transition_letter:
            return self.suffix_link_with_transition_letter[c]
        if c in self.children:
            self.suffix_link_with_transition_letter[c] = self
            return self
        self.suffix_link_with_transition_letter[c] = self.get_suffix_link().get_suffix_link_with_transition_letter(c)
        return self.suffix_link_with_transition_letter[c]

    def get_terminal_link(self):
        if self.parent is None:
            self.terminal_link = self
            return self.terminal_link
        if self.parent.parent is None:
            self.terminal_link = self.parent
            return self.terminal_link
        if self.terminal_link is not None:
            return self.terminal_link
        
        terminal_link_with_transition_letter = self.parent.get_suffix_link().get_terminal_link_with_transition_letter(self.c)
        if self.c not in terminal_link_with_transition_letter.children or (not terminal_link_with_transition_letter.children[self.c].is_word):
            self.terminal_link = terminal_link_with_transition_letter
        else:
            self.terminal_link = terminal_link_with_transition_letter.children[self.c]
        return self.terminal_link

    def get_terminal_link_with_transition_letter(self, c):
        if self.parent is None:
            self.terminal_link_with_transition_letter[c] = self
            return self
        if c in self.terminal_link_with_transition_letter:
            return self.terminal_link_with_transition_letter[c]
        if c in self.children and self.children[c].is_word:
            self.terminal_link_with_transition_letter[c] = self
            return self
        self.terminal_link_with_transition_letter[c] = self.get_suffix_link().get_terminal_link_with_transition_letter(c)
        return self.terminal_link_with_transition_letter[c]

class Solution:
    def get_suffixes_with_transition_letter(self, trie, c):
        next_trie = trie.get_suffix_link_with_transition_letter(c)
        if c not in next_trie.children:
            return (next_trie, [])
        next_trie = next_trie.children[c]
        suffixes = []
        current_node = next_trie
        while current_node.parent is not None:
            if current_node.is_word:
                suffixes.append(current_node.word_index)
            current_node = current_node.get_terminal_link()
        return (next_trie, suffixes)

    def minimumCost(self, target: str, words: list[str], costs: list[int]) -> int:
        root = TrieNode('', False, -1)
        for i in range(len(words)):
            root.insert(words[i], i, costs)

        # dp[i]: minimum cost for target[:i]
        dp = [float('inf') for i in range(len(target)+1)]
        dp[0] = 0

        current_node = root
        for i in range(1, len(target)+1):
            c = target[i-1]
            current_node, suffixes = self.get_suffixes_with_transition_letter(current_node, c)
            for word_index in suffixes:
                dp[i] = min(dp[i], costs[word_index] + dp[i - len(words[word_index])])
        if dp[-1] == float('inf'):
            return -1
        return dp[-1]
60400