<p>You are given an array of strings <code>words</code> and a string <code>target</code>.</p>

<p>A string <code>x</code> is called <strong>valid</strong> if <code>x</code> is a <span data-keyword="string-prefix">prefix</span> of <strong>any</strong> string in <code>words</code>.</p>

<p>Return the <strong>minimum</strong> number of <strong>valid</strong> strings that can be <em>concatenated</em> to form <code>target</code>. If it is <strong>not</strong> possible to form <code>target</code>, 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">words = [&quot;abc&quot;,&quot;aaaaa&quot;,&quot;bcdef&quot;], target = &quot;aabcdabc&quot;</span></p>

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

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

<p>The target string can be formed by concatenating:</p>

<ul>
	<li>Prefix of length 2 of <code>words[1]</code>, i.e. <code>&quot;aa&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[2]</code>, i.e. <code>&quot;bcd&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[0]</code>, i.e. <code>&quot;abc&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">words = [&quot;abababab&quot;,&quot;ab&quot;], target = &quot;ababaababa&quot;</span></p>

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

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

<p>The target string can be formed by concatenating:</p>

<ul>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abcdef&quot;], target = &quot;xyz&quot;</span></p>

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

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

<ul>
	<li><code>1 &lt;= words.length &lt;= 100</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 5 * 10<sup>3</sup></code></li>
	<li>The input is generated such that <code>sum(words[i].length) &lt;= 10<sup>5</sup></code>.</li>
	<li><code>words[i]</code> consists only of lowercase English letters.</li>
	<li><code>1 &lt;= target.length &lt;= 5 * 10<sup>3</sup></code></li>
	<li><code>target</code> consists only of lowercase English letters.</li>
</ul>

class Solution:
    def __init__(self):
        self.MODS = [1700000000000000071, 1000000007, 1000000009]
        #self.di = dict()
        self.hs = set()
        self.prefix = [] # Rabin-Karp prefix
        self.pows = []
    def populateAttributes(self, words, target, num_mods):
        
        def getKey(c):
            return ord(c) - ord("a") + 1
        
        coeff = 27
        for word in words:
            keys = [0 for _ in range(num_mods)]
            for c in word:
                for i in range(len(keys)):
                    keys[i] *= coeff
                    keys[i] += getKey(c)
                    keys[i] %= self.MODS[i]
                self.hs.add(tuple(keys))
        
        self.pows.append( [1 for _ in range(num_mods)] )
        for i in range(1, len(target)):
            x = [0 for _ in range(num_mods)]
            for j in range(num_mods):
                x[j] = (self.pows[-1][j] * coeff) % self.MODS[j]
            self.pows.append(x)
        
        self.prefix.append( [getKey(target[0]) for _ in range(num_mods)] )
        for i in range(1, len(target)):
            x = [0 for _ in range(num_mods)]
            for j in range(num_mods):
                x[j] = (self.prefix[-1][j] * coeff + getKey(target[i])) % self.MODS[j]
            self.prefix.append(x)
                
                
    def substringKey(self, L, R):
        #key = copy.deepcopy(self.prefix[R])
        key = self.prefix[R][:]
        if L == 0:
            return tuple(key)
        
        #decr = copy.deepcopy(self.prefix[L - 1])
        decr = self.prefix[L - 1][:]
        idx = R - L + 1
        
        # print("L:", L, "R:", R)
        # print("idx:", idx)
        mult = self.pows[idx]

#         print("mult:", mult)
#         print("key before:", key)
#         print("decr:", decr)
        
        for i in range(len(key)):
            decr[i] *= mult[i]
            decr[i] %= self.MODS[i]
            key[i] -= decr[i]
            if key[i] < 0:
                key[i] += self.MODS[i]
        
        # print("key after:", key)
        
        return tuple(key)
           
        
    def isValid(self, key):
        return key in self.hs
    
    def single_repeated_char(self, s: str) -> bool:
        for i in range(len(s) - 1):
            if s[i] != s[i + 1]:
                return False
        return True

    def get_this(self, words: list[str], target: str) -> int:
        c = target[0]
        best = 0
        for word in words:
            for i in range(len(word)):
                if word[i] == c:
                    best = max(best, i + 1)
                else:
                    break
        return best
    
    def get_RLE(self, target):
        RLE = [target[0], 0]
        for c in target:
            if c == RLE[-2]:
                RLE[-1] += 1
            else:
                RLE.append(c)
                RLE.append(1)
        return RLE
        
    def minValidStrings(self, words: List[str], target: str) -> int:
        ## some massive DP
        ## Rabin-Karp
        
        #"""
        ## heuristic optimization, break it down into RLE's
        RLE = self.get_RLE(target)
        try_heuristic = True
        for i in range(1, len(RLE), 2):
            if RLE[i] < 100:
                try_heuristic = False
                break
        
        #if self.single_repeated_char(target):
        if try_heuristic is True:
            ans = 0
            for i in range(0, len(RLE), 2):
                c = RLE[i]
                count = RLE[i + 1]
                print("count:", count)
                
                max_repeated_char_prefix_len = self.get_this(words, c * count)
                
                a = count
                b = max_repeated_char_prefix_len
                if b == 0:
                    return -1
                ans += a // b + (a % b != 0)
            return ans
        #"""
        
        num_mods = 1
        self.populateAttributes(words, target, num_mods)
        
#         print("hs:", self.hs)
#         print("prefix:", self.prefix)
#         print("pows:", self.pows)
        
        DP = [float("inf") for _ in range(len(target))]
#         for i in range(len(DP)):
#             # print("DP:", DP)
#             key = self.substringKey(0, i)
#             # print("key:", key)
#             if self.isValid(key):
#                 DP[i] = 1
#                 continue
            
#             for L in reversed(range(1, i + 1)):
#                 key = self.substringKey(L, i)
#                 if self.isValid(key) and DP[L - 1] != float("inf"):
#                     DP[i] = min(DP[i], DP[L - 1] + 1)
        for i in range(len(DP)):
            if i == 0:
                for R in range(len(DP)):
                    key = self.substringKey(0, R)
                    if self.isValid(key):
                        DP[R] = 1
                    else:
                        break
                continue
            if DP[i] == float("inf"):
                key = self.substringKey(i, i)
                if not self.isValid(key):
                    return -1
            for R in range(i, len(DP)):
                key = self.substringKey(i, R)
                if not self.isValid(key):
                    break
                DP[R] = min(DP[R], DP[i - 1] + 1)
            
            
        
        
        # print("DP:", DP)
        if DP[-1] == float("inf"):
            return -1
        return DP[-1]
        
26819