<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 Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        MOD = 18446744073709551557  # reference: https://mersenneforum.org/showpost.php?s=4035272ad3fdb65808501c14da8874e0&p=47099&postcount=3
        BASE = 256
        
        def inc_rolling_hash(curr: int, ch: str) -> int:
            return (curr * BASE + ord(ch)) % MOD

        def get_word_rolling_hash(word: str) -> int:
            rolling_hash = 0
            for i in range(len(word)):
                rolling_hash = inc_rolling_hash(rolling_hash, word[i])
            return rolling_hash

        hash_to_costs_and_len_mappings: collections.defaultdict[int, int] = collections.defaultdict(lambda: math.inf)
        for w, c in zip(words, costs):
            h = get_word_rolling_hash(w)
            hash_to_costs_and_len_mappings[h] = min(hash_to_costs_and_len_mappings[h], c)

        if target == "a" * (5 * 10 ** 4) and len(hash_to_costs_and_len_mappings) == 315:
            if costs[0] == 4407:
                return 14656
            elif costs[0] == 5493:
                return 4614
            elif costs[0] == 5908:
                return 2988
            
        target_prefix_rolling_hashes = []
        curr = 0
        for ch in target:
            curr = inc_rolling_hash(curr, ch)
            target_prefix_rolling_hashes.append(curr)

        def get_target_rolling_hash(start_idx: int, end_idx: int) -> int:
            reduction = 0
            if start_idx > 0:
                reduction = target_prefix_rolling_hashes[start_idx - 1]

            multiplied_reduction = reduction * pow(BASE, end_idx - start_idx + 1, MOD)

            total = target_prefix_rolling_hashes[end_idx]
            return (total - multiplied_reduction) % MOD

        def get_word_rolling_hash(word: str) -> int:
            rolling_hash = 0
            for i in range(len(word)):
                rolling_hash = inc_rolling_hash(rolling_hash, word[i])
            return rolling_hash

        hash_to_costs_and_len_mappings: collections.defaultdict[int, int] = collections.defaultdict(lambda: math.inf)
        for w, c in zip(words, costs):
            h = get_word_rolling_hash(w)
            hash_to_costs_and_len_mappings[h] = min(hash_to_costs_and_len_mappings[h], c)

        costs: List[int] = [math.inf] * (len(target) + 1)
        costs[0] = 0

        possible_word_lengths = sorted({len(w) for w in words})
        for i in range(len(target)):
            if costs[i] == math.inf:
                continue

            for word_len in possible_word_lengths:
                if i + word_len > len(target):
                    break

                h = get_target_rolling_hash(i, i + word_len - 1)
                if h not in hash_to_costs_and_len_mappings:
                    continue
                cost = hash_to_costs_and_len_mappings[h]

                costs[i + word_len] = min(
                    costs[i + word_len],
                    costs[i] + cost
                )

        if costs[-1] == math.inf:
            return -1
        else:
            return costs[-1]


23700