<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>4</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>4</sup></code></li>
	<li><code>target</code> consists only of lowercase English letters.</li>
</ul>


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

        def ex_gcd(a, b):
            if b==0:
                return a, 1, 0
            
            gcd, x1, y1 = ex_gcd(b, a%b)

            x = y1
            y = x1 - (a//b)*y1
            return gcd, x, y
        tn = len(target)


        def one_round():
            nonlocal tn
            times = 4

            tries=[(256, 1000_000_000-3), (256, 1000_000_000+3),
                    (257, 1000_000_000+3), (257, 1000_000_000-3),
                    (256, 1000_000_00+3), (256, 1000_000_00-3),
                    (257, 1000_000_00+3), (257, 1000_000_00-3),]

            
            prehash = [set() for i in range(times)]

            n = len(words)

            def hash1(pre, vocab, ch, modn):
                cur = pre*vocab+ord(ch)
                #print(f"pre:{pre}, vocab:{vocab}, ch:{ord(ch)}, modn:{modn} ")
                return cur%modn


            for i in range(n):
                w= words[i]
                #print(f"i:{i} w:{w}")

                pre = [0 for k in range(times)]
                for j in range(len(w)):
                    for k in range(times):
                        cur = hash1(pre[k],tries[k][0], w[j], tries[k][1]) #

                    #if cur not in prehash:
                    #    prehash[cur] = []
                    #prehash[cur].append((i,j))
                        prehash[k].add(cur)
                        pre[k] = cur
                        #print(f"cur: {cur}, prehash: {prehash[k]}")
            #print(f'prehash0: {prehash[0]}')

            h1 = [[0 for i in range(tn)] for k in range(times)]
            pre = [0 for k in range(times)]
            b=1
            bases = [[0 for i in range(tn)] for k in range(times)]
            for i in range(tn-1, -1, -1):
                for k in range(times):
                    modn = tries[k][1]
                    if i==tn-1:
                        bases[k][i] =1
                    else:
                        bases[k][i] = (bases[k][i+1]*tries[k][0])%modn

                    h1[k][i] = (ord(target[i])*bases[k][i] + pre[k])%modn
                    pre[k] = h1[k][i]

            
            mod_inverse = [[0 for i in range(tn)] for k in range(times)]
            for k in range(times):
                for i in range(tn-1, -1,-1):
                    modn = tries[k][1]
                    gcd, x, y = ex_gcd(bases[k][i], modn)
                    #print(f"k:{k}, i:{i}, baseki:{bases[k]}, modn:{modn}")
                    if gcd!=1:
                        raise ValueError
                    mod_inverse[k][i] = x
                
                
            #print(f"ok1 tn:{tn}, target:{target}\n, h1:{h1}")


            # a*x + b*y = 1
            # b: modn
            # a: base (256^k)
            # base * x + modn*y =1
            # hashpre: all - tail
            # hashleft: rankm*(all-tail)
            def prefix_hash(k, full, right, pos,  modn):
                left = (full - right)%modn
                #print(f"pos:{pos}")
                lefthash = (mod_inverse[k][pos]*left)%modn
                return lefthash
            # bcd: (256*98 +99)*256+100 = 6447972


            def bsect(st):
                l=st
                r = tn-1
                cnt = 0
                #print(f"bsect l:{l}, r:{r}")
                if ord(target[st]) not in prehash[0]:
                    return 0
                #print(h1[0])
                while l<r:
                    
                    m = (l+r)//2 
                    ok = True
                    for k in range(times):
                        modn = tries[k][1]
                        hasht= h1[k][st]
                        if m+1!=tn-1:
                            hasht = prefix_hash(k, h1[k][st], h1[k][m+2], m+1, modn)
                        #if st ==2:
                            #print(f"st:{st}, l:{l}, r:{r}, m:{m}, ht: {hasht}")

                        if hasht not in prehash[k]:
                            #print(f"not in st:{st}, l:{l}, r:{r}, m:{m}, ht: {hasht}")
                            ok = False
                            break
                    if ok:
                        l=m+1
                        #if st ==2:
                            #print(f"in ht:{hasht}")

                    else:
                        #if st ==2:
                            #print(f"not in ht:{hasht}")
                        r=m
                return l-st+1
                

            tn = len(target)

            best = [1000_000 for i in range(tn+1)]

            best[tn] = 0

            bitlen = 20

            rangem = [[1000_000 for i in range(tn+1)] for j in range(bitlen)]
            for i in range(bitlen):
                rangem[i][tn] = 0

            twos = [1 for i in range(bitlen)]
            for i in range(1,bitlen):
                twos[i] = 2*twos[i-1]

            #print("ok2")
            base = 1
            for i in range(tn-1, -1, -1): # max 5*10000
                #print("ok3")
                # tail = s[i:] TLE
                #clen = trie.prefixLen(target, i)
                #print('')
                clen = bsect(i)
                #print(f"i:{i}, clen:{clen}")

                if clen>0:
                    tailmini = 1000_000
                    if clen == (tn-i):
                        tailmini=0
                        

                    #print(f"t:{t}, tn:{tn-1}, tailmini:{tailmini}")
                    for k in range(bitlen):
                        l = twos[k]
                        #print(f"best:{best}")
                        #print(f"k:{k}, clen:{clen}, i:{i} l:{l}, rangemk:{rangem[k]}")
                        if clen>=l:
                            minit = min(rangem[k][i+1], rangem[k][i+clen-l+1])
                            tailmini = min(minit, tailmini)

                            #print(f"celn>l: tailmini:{tailmini}")
                        else:
                            #print("break")
                            break
                    
                    best[i] = tailmini +1
                    #print(f"i:{i}, tailmini:{tailmini}")
                #print(f"i:{i}, best{best}")
                rangem[0][i] = best[i]
                for k in range(1,bitlen):
                    l = twos[k-1]
                    if i + l <=tn:
                        rangem[k][i] = min(rangem[k-1][i], rangem[k-1][i+l])
                    else:
                        break
                #print(f'i:{i}\n')
            



            return best[0] if best[0]<1000_000 else -1
        vocabs = [257,256]
        mods = [1000_000_000+3, 1000_000_000-3, 1000_000_00+3, 1000_000_00-3]

        best0 = one_round()
        return best0



        
66408