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


PRIME1 = 31
PRIME2 = 1000000007
class RKHash:
    def __init__(self):
        self.val = 0
        self.sz  = 0
        self.mul = 1
    
    def append(self, intval):
        self.val *= PRIME1
        self.val += intval+1
        self.val %= PRIME2
        self.sz  += 1
        self.mul *= PRIME1
        self.mul %= PRIME2
    
    def prepend(self, intval):
        self.val += (intval+1)*self.mul
        self.val %= PRIME2
        self.sz  += 1
        self.mul *= PRIME1
        self.mul %= PRIME2
    
    def __hash__(self):
        return (self.val,self.sz)
    
    def key(self):
        return (self.val,self.sz)

    def copy(self):
        ret = RKHash()
        ret.val = self.val
        ret.sz  = self.sz
        ret.mul = self.mul
        return ret
    
    def test(self):
        sample = [1,2,3,4,5]
        rk1,rk2 = RKHash(),RKHash()
        for x in sample:
            rk1.append(x)
        for x in reversed(sample):
            rk2.prepend(x)
        assert(rk1.val == rk2.val)
        assert(rk1.sz == rk2.sz)

class RKSubstringHash:
    def __init__(self, given):
        self.N = len(given)    
        self.rkprefix = [0]*self.N
        self.rkmul    = [0]*self.N
        rk = RKHash()
        for i,x in enumerate(given):
            rk.append(x)
            self.rkprefix[i] = rk.key()
            self.rkmul[i] = rk.mul

        self.rksuffix = [0]*self.N
        rk = RKHash()
        for i in range(self.N-1,-1,-1):
            rk.prepend(given[i])
            self.rksuffix[i] = rk.key()
    
    def test_substring(self, given, beg:int,end:int):
        assert(beg<end)
        rk = RKHash()
        for i in range(beg,end):
            rk.append(given[i])
        #print(self.rksuffix)
        subkey = self.substring(beg,end)
        print(beg,end,'test_substring', given[beg:end] , rk.key(), subkey)
        assert(rk.key() == subkey)
        
    def substring(self, beg:int,end:int):
        assert(beg<end)
        if end >= self.N:
            #print('substring returning suffix', self.rksuffix)
            return self.rksuffix[beg]
        if 0 == beg:
            return self.rkprefix[end-1]
        
        eprefix = self.rkprefix[end-1][0]
        bprefix = self.rkprefix[beg-1][0]
        bprefix *= self.rkmul[end-beg-1]
        bprefix %= PRIME2
        rval = (eprefix-bprefix)%PRIME2
        return (rval,end-beg)

class SegmentTreeRMQ:
    '''
    segment_tree.py file is part of Algosnippet.
    Algosnippet is a collection of practice data-structures and algorithms
    Copyright (C) 2024  Kamanashis Roy
    Algosnippet is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
    Algosnippet is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    You should have received a copy of the GNU General Public License
    along with Algosnippet.  If not, see <https://www.gnu.org/licenses/>.
    '''

    def __init__(self, Ngiven:int, defaultVal:int = -1):
        depth = 0
        while (1<<depth) < Ngiven:
            depth += 1

        INFLO = (defaultVal,-1)
        self.N = 1<<depth
        self.nodes = [ INFLO for _ in range((self.N<<1)+2)]
        self.rightMost = [ i for i in range((self.N<<1)+2)]
        self.leftMost = [ i for i in range((self.N<<1)+2)]
        # N = 4
        # [ filler 0 ] [ root Node 1 ] 2 3 [ Internal nodes 4 5 6 7 ] [ Leaves 8 9 10 11 12 13 14 15 ]
        for i in range(self.N-1,0,-1):
            self.leftMost[i] = self.leftMost[i<<1]
            self.rightMost[i] = self.rightMost[(i<<1)+1]

    def fill(self,aNums):
        assert((self.N+len(aNums)-1) < len(self.nodes))
        for i,x in enumerate(aNums):
            self.nodes[i+self.N] = (x,i)
        
        for i in range(self.N-1,0,-1):
            self.nodes[i] = max(self.nodes[i<<1],self.nodes[(i<<1)+1])

    def __setitem__(self, i:int, givenVal:int) -> None:
        '''
        Procedure
        =========
            - sets the value at the leaf
            - go up towards the root and update the maximum value
        '''
        assert((self.N+i) < len(self.nodes))
        curr = self.N+i
        val = (givenVal,i)
        if val <= self.nodes[curr]:
            return # do not update
        self.nodes[curr] = val
        while curr > 1:
            # get parent
            parent = curr >> 1
            if  self.nodes[parent] >= val:
                break # do not update
            self.nodes[parent] = val
            curr = parent

    def __getitem__(self, i:int) -> int:
        assert((self.N+i) < len(self.nodes))
        return self.nodes[self.N+i]
    
    def queryMaxAll(self):
        return self.nodes[1]
    
    def queryMaxLeft(self, i:int) -> int:
        '''
        Return the max score saved in range of [0,i] inclusive
        '''
        curr = self.N+i
        result = self.nodes[curr]
        path = []
        while curr > 1:
            parent = curr >> 1
            path.append((parent,curr&1))
            curr = parent

        while path:
            curr,odd = path.pop()
            if odd:
                # when we are going for right child
                # take best result from left
                left = curr<<1
                result = max(result, self.nodes[left])
            else:
                # when we are going for left chld, we cannot take memo
                pass
        return result
    
    def queryMax(self, givenLeft, givenRight, defaultVal = None):
        '''
        Return the maximum value between beg and end
        '''
        assert(givenLeft <= givenRight)
        assert((self.N+givenRight) < len(self.nodes))
        
        ret = max(self.nodes[self.N+givenLeft],self.nodes[self.N+givenRight])
        if defaultVal is not None:
            ret = max((defaultVal,-1),ret)
        stack = [1]
        while stack:
            cur = stack.pop()
            for child in (cur<<1,(cur<<1)+1):
                rightMost = self.rightMost[child]
                if rightMost < (self.N+givenLeft):
                    continue
                leftMost = self.leftMost[child]
                if leftMost > (self.N+givenRight):
                    continue

                if rightMost <= (self.N+givenRight) and leftMost >= (self.N+givenLeft):
                    ret = max(ret,self.nodes[child])
                    continue
                    
                if defaultVal is not None and self.nodes[child][0] <= defaultVal:
                    continue

                stack.append(child)
                
        return ret

    def printNodes(self, beg,end):
        print(self.nodes[self.N+beg:self.N+end])

class PrefixTrie:
    def __init__(self, val, rk = None):
        self.val = val
        self.children = [None]*26
        if rk is None:
            self.rk = RKHash()
        else:
            self.rk = rk.copy()
        if val is not None:
            self.rk.append(val)

    def __getitem__(self, i):
        return self.children[i]

    def __setitem__(self, i, val):
        self.children[i] = val

    def add(self, given):
        cur = self
        ORDA = ord('a')
        for x in given:
            xval = ord(x)-ORDA
            if cur[xval] is None:
                cur[xval] = PrefixTrie(xval, cur.rk)
            cur = cur[xval]

    def find(self, given, beg):
        cur = self
        ORDA = ord('a')
        gn = len(given)
        for i in range(beg,gn):
            xval = ord(given[i])-ORDA
            if cur[xval] is None:
                return
            yield i+1,cur[xval].rk
            cur = cur[xval]

    def getHashes(self, output):
        assert( (self.rk.val,self.rk.sz) not in output)
        output[(self.rk.val,self.rk.sz)] = self
        for x in self.children:
            if x is not None:
                x.getHashes(output)
        
def strToAscii(given):
    ORDA = ord('a')
    ret = []
    for x in given:
        xval = ord(x)-ORDA
        ret.append(xval)
    return ret

class fingerRMQ:
    '''
    fingerRMQ.py file is part of Algosnippet.
    Algosnippet is a collection of practice data-structures and algorithms
    Copyright (C) 2021  Kamanashis Roy
    Algosnippet is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
    Algosnippet is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    You should have received a copy of the GNU General Public License
    along with Algosnippet.  If not, see <https://www.gnu.org/licenses/>.
    '''


    def __init__(self, aN, defaultVal=-1):
        self.N = aN
        depth = 1
        while (1<<depth) < self.N:
            depth += 1
        
        self.INFLO = (defaultVal, -1)
        self.N = 1<<depth
        self.nodes = [self.INFLO]*((self.N+1)<<1)
    
    def fill(self,aNums):
        for i,x in enumerate(aNums):
            self.nodes[i+self.N] = (x,i)
        
        for i in range(self.N-1,0,-1):
            self.nodes[i] = max(self.nodes[i<<1],self.nodes[(i<<1)+1])

    def __getitem__(self, i:int):
        cur = self.N+i
        return self.nodes[cur]

    def __setitem__(self, i:int, val:int):
        cur = self.N+i
        if val == self.nodes[cur][0]:
            return
        self.nodes[cur] = (val,i)
        while cur > 1:
            parent = cur>>1
            if self.nodes[parent] >= (val,i):
                break
            self.nodes[parent] = max(self.nodes[parent], (val,i))
            cur = parent

    def rmq(self, beg, size):
        if size <= 0:
            return self.INFLO

        if size < 8:
            ret = self.INFLO
            for i in range(beg,beg+size):
                ret = max(ret,self.nodes[self.N+i])
            return ret

        left = self.N+beg
        right = left+size-1
        cur = right
        ret = self.nodes[cur]
        covered_left = cur

        depth = 0
        while cur > 1:
            parent = cur>>1
            if cur&1: # if right child
                # we are good
                subtree_beg = covered_left - (1<<depth)
                if subtree_beg >= left:
                    # go ahead
                    ret = max(ret,self.nodes[parent])
                    covered_left = subtree_beg
                    if left == subtree_beg:
                        return ret
                else:
                    return max(ret,self.rmq(beg, covered_left-left))
            else: # if left child
                return max(ret,self.rmq(beg, covered_left-left))
            cur = parent
            depth+=1

class Solution:
    def minValidStrings(self, words: List[str], givenTarget: str) -> int:
        N = len(givenTarget)
        target = strToAscii(givenTarget)

        MPREFIX = 0
        lookup = set()
        for w in words:
            MPREFIX = max(MPREFIX,len(w))
            rk = RKHash()
            wi = strToAscii(w)
            for x in wi:
                rk.append(x)
                lookup.add(rk.key())
            
        INF = float('Inf')
        NINF = float('-Inf')

        subLookup = RKSubstringHash(target)

        def possible(beg,end):
            assert(beg<end)
            #subLookup.test_substring(target, beg, end)
            hcode = subLookup.substring(beg,end)
            if hcode in lookup:
                return True
            return False

        #memo = fingerRMQ(N+2,NINF)
        memo = SegmentTreeRMQ(N+2,NINF)
        memo[N] = 0
        prevHash = RKHash()
        prevHash.test()
        ORDA = ord('a')
        for pos in range(len(target)-1,-1,-1):

            lo = pos
            hi = min(len(target)-1, pos+MPREFIX)
            while lo<hi:
                mid = (lo+hi)>>1
                if not possible(pos,mid+1):
                    hi = mid-1
                else:
                    if mid == lo:
                        break
                    lo = mid
            # found best match in 
            if hi >= pos:
                if possible(pos,hi+1):
                    lo = hi
            lo = max(lo,pos)
            if not possible(pos,lo+1):
                continue
            #print(pos, 'best match', givenTarget[pos:lo+1])
            # longest possible prefix match is at lo
            # find the minimum value in range pos and lo
            if lo == pos: # single character match
                memo[pos] = memo[pos+1][0]-1
                continue
            loc = memo.queryMax(pos+1,lo+1)
            #loc = memo.rmq(pos+1,lo-pos+1)
            #memo.printNodes(0,N+1)
            #print(pos+1,lo+1, 'queryMax', loc)
            if loc[1] != -1:
                memo[pos] = loc[0]-1

        #memo.printNodes(0,N+1)
        result = memo[0]
        result = -result[0]
        if result > N:
            return -1
        return result
56343