<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 LazySegmentTree:
    def __init__(self, data, default=inf, func=min):
        """initialize the lazy segment tree with data"""
        self._default = default
        self._func = func

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i<<1], self.data[i<<1|1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        # Let the children know of the queries
        q, self._lazy[idx] = self._lazy[idx], 0

        self._lazy[idx<<1] += q
        self._lazy[idx<<1|1] += q
        self.data[idx<<1] += q
        self.data[idx<<1|1] += q

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[idx<<1], self.data[idx<<1|1]) + self._lazy[idx]
            idx >>= 1

    def add(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start + self._size
        stop = stop + self._size
        cr=cl=False
        while start < stop:
            if cl:
                sp=start-1
                self.data[sp]=self._func(self.data[sp<<1],self.data[sp<<1|1])+self._lazy[sp]
            if cr:
                self.data[stop]=self._func(self.data[stop<<1],self.data[stop<<1|1])+self._lazy[stop]
            if start & 1:
                self._lazy[start] += value
                self.data[start] += value
                start += 1
                cl=True
            if stop & 1:
                stop -= 1
                self._lazy[stop] += value
                self.data[stop] += value
                cr=True
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        start-=1
        while stop>0:
            if cl:
                self.data[start]=self._func(self.data[start<<1],self.data[start<<1|1])+self._lazy[start]
            if cr and (not cl or start!=stop):
                self.data[stop]=self._func(self.data[stop<<1],self.data[stop<<1|1])+self._lazy[stop]

            start>>=1
            stop>>=1
    def query(self, start, stop, default=inf):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        # Apply all the lazily stored queries
        self._update(start)
        self._update(stop - 1)

        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)
class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        n=len(target)
        mod=2**63-1
        iv=pow(27,-1,mod)
        f=lambda x:ord(x)-ord("a")+1
        def radr(x,c):
            return (x*27+c)%mod
        def subl(x,c,p):
            return (x-c*p)%mod
        def subr(x,c):
            return ((x-c)*iv)%mod
        s=set()
        for w in words:
            x=0
            for c in w:
                x=radr(x,f(c))
                s.add(x)
        
        
        cur=0
        left=[-1]*n
        beg=0
        p=1
        for i in range(n):
            cur=radr(cur,f(target[i]))
            
            while cur not in s:
                cur=subl(cur,f(target[beg]),p)
                beg+=1
                p=(p*iv)%mod
                if beg>i:break
            else:
                left[i]=beg
            p=(p*27)%mod
        
        mem=[-2]*n
        def g(r):
            if mem[r]!=-2:
                return mem[r]
            if T[r] in s:
                return 1
            else:
                l=left[r]
                if l==-1:
                    res=inf
                else:
                    res=1+min(g(v)for v in range(l-1,r))
                mem[r]=res
                return res
        o=[0]*n
        st=LazySegmentTree(o)
        for r in range(n):
            if left[r]==-1:
                o[r]=inf
            elif left[r]==0:
                o[r]=1
            else:
                o[r]=1+st.query(left[r]-1,r)
            st.add(r,r+1,o[r])
        return o[n-1] if o[n-1]!=inf else -1
        
68086