binary search on robin-karp substring hash while doing Dynamic Programming
Intuition\n\nWe can get to a result if we travarse the given "target" from the end and build a bottom-up memoization table we call "memo".\n\nAnd our result wil
# Intuition\n\nWe can get to a result if we travarse the given "target" from the end and build a bottom-up memoization table we call "memo".\n\nAnd our result will be at the beginning "memo[0]".\n```\nfor i in range(len(target)-1,-1,-1):\n    memo[i] = memo[i+longest match] + 1\nreturn memo[0] if memo[0] < N else -1\n```\n\nBut finding the longest match can be naive if we go through all the words to check for best match.\n\nInstead we can do binary search while checking if it is "possible" to find match of substring.\n\n```\nlo = pos\nhi = len(target)-1\nwhile lo<hi:\n    mid = (lo+hi)>>1\n    if not possible(pos,mid+1):\n        hi = mid-1\n    else:\n        if mid == lo:\n            break\n        lo = mid\n# found best match in \nif hi >= pos:\n    if possible(pos,hi+1):\n        lo = hi\nlo = max(lo,pos)\nif not possible(pos,lo+1):\n    continue\n```\n\n\n# Approach\n\nAs discussed above we traversed the given "target" from the end, while building a memoization table "memo".\n\nWe used rolling hash `RKSubstringHash` to quickly get the hash of a substring.\n\nWe used a set called `lookup` to see if the substring hash is there as prefix in the words. \n\nFinally to get the minimum cost, we used a `SegmentTreeRMQ` to `queryMax()` the best value in the substring range. \n\n# Complexity\n- Time complexity:\n\n`O(N*log(100))`\n\n- Space complexity:\n`O(N*log(N))`\n\n# Code\n```python3 []\n\nPRIME1 = 31\nPRIME2 = 1000000007\nclass RKHash:\n    def __init__(self):\n        self.val = 0\n        self.sz  = 0\n        self.mul = 1\n    \n    def append(self, intval):\n        self.val *= PRIME1\n        self.val += intval+1\n        self.val %= PRIME2\n        self.sz  += 1\n        self.mul *= PRIME1\n        self.mul %= PRIME2\n    \n    def prepend(self, intval):\n        self.val += (intval+1)*self.mul\n        self.val %= PRIME2\n        self.sz  += 1\n        self.mul *= PRIME1\n        self.mul %= PRIME2\n    \n    def __hash__(self):\n        return (self.val,self.sz)\n    \n    def key(self):\n        return (self.val,self.sz)\n\n    def copy(self):\n        ret = RKHash()\n        ret.val = self.val\n        ret.sz  = self.sz\n        ret.mul = self.mul\n        return ret\n    \n    def test(self):\n        sample = [1,2,3,4,5]\n        rk1,rk2 = RKHash(),RKHash()\n        for x in sample:\n            rk1.append(x)\n        for x in reversed(sample):\n            rk2.prepend(x)\n        assert(rk1.val == rk2.val)\n        assert(rk1.sz == rk2.sz)\n\nclass RKSubstringHash:\n    def __init__(self, given):\n        self.N = len(given)    \n        self.rkprefix = [0]*self.N\n        self.rkmul    = [0]*self.N\n        rk = RKHash()\n        for i,x in enumerate(given):\n            rk.append(x)\n            self.rkprefix[i] = rk.key()\n            self.rkmul[i] = rk.mul\n\n        self.rksuffix = [0]*self.N\n        rk = RKHash()\n        for i in range(self.N-1,-1,-1):\n            rk.prepend(given[i])\n            self.rksuffix[i] = rk.key()\n    \n    def test_substring(self, given, beg:int,end:int):\n        assert(beg<end)\n        rk = RKHash()\n        for i in range(beg,end):\n            rk.append(given[i])\n        #print(self.rksuffix)\n        subkey = self.substring(beg,end)\n        print(beg,end,\'test_substring\', given[beg:end] , rk.key(), subkey)\n        assert(rk.key() == subkey)\n        \n    def substring(self, beg:int,end:int):\n        assert(beg<end)\n        if end >= self.N:\n            #print(\'substring returning suffix\', self.rksuffix)\n            return self.rksuffix[beg]\n        if 0 == beg:\n            return self.rkprefix[end-1]\n        \n        eprefix = self.rkprefix[end-1][0]\n        bprefix = self.rkprefix[beg-1][0]\n        bprefix *= self.rkmul[end-beg-1]\n        bprefix %= PRIME2\n        rval = (eprefix-bprefix)%PRIME2\n        return (rval,end-beg)\n\nclass SegmentTreeRMQ:\n    \'\'\'\n    segment_tree.py file is part of Algosnippet.\n    Algosnippet is a collection of practice data-structures and algorithms\n    Copyright (C) 2024  Kamanashis Roy\n    Algosnippet is free software: you can redistribute it and/or modify\n    it under the terms of the GNU General Public License as published by\n    the Free Software Foundation, either version 3 of the License, or\n    (at your option) any later version.\n    Algosnippet is distributed in the hope that it will be useful,\n    but WITHOUT ANY WARRANTY; without even the implied warranty of\n    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n    GNU General Public License for more details.\n    You should have received a copy of the GNU General Public License\n    along with Algosnippet.  If not, see <https://www.gnu.org/licenses/>.\n    \'\'\'\n\n    def __init__(self, Ngiven:int, defaultVal:int = -1):\n        depth = 0\n        while (1<<depth) < Ngiven:\n            depth += 1\n\n        INFLO = (defaultVal,-1)\n        self.N = 1<<depth\n        self.nodes = [ INFLO for _ in range((self.N<<1)+2)]\n        self.rightMost = [ i for i in range((self.N<<1)+2)]\n        self.leftMost = [ i for i in range((self.N<<1)+2)]\n        # N = 4\n        # [ filler 0 ] [ root Node 1 ] 2 3 [ Internal nodes 4 5 6 7 ] [ Leaves 8 9 10 11 12 13 14 15 ]\n        for i in range(self.N-1,0,-1):\n            self.leftMost[i] = self.leftMost[i<<1]\n            self.rightMost[i] = self.rightMost[(i<<1)+1]\n\n    def fill(self,aNums):\n        assert((self.N+len(aNums)-1) < len(self.nodes))\n        for i,x in enumerate(aNums):\n            self.nodes[i+self.N] = (x,i)\n        \n        for i in range(self.N-1,0,-1):\n            self.nodes[i] = max(self.nodes[i<<1],self.nodes[(i<<1)+1])\n\n    def __setitem__(self, i:int, givenVal:int) -> None:\n        \'\'\'\n        Procedure\n        =========\n            - sets the value at the leaf\n            - go up towards the root and update the maximum value\n        \'\'\'\n        assert((self.N+i) < len(self.nodes))\n        curr = self.N+i\n        val = (givenVal,i)\n        if val <= self.nodes[curr]:\n            return # do not update\n        self.nodes[curr] = val\n        while curr > 1:\n            # get parent\n            parent = curr >> 1\n            if  self.nodes[parent] >= val:\n                break # do not update\n            self.nodes[parent] = val\n            curr = parent\n\n    def __getitem__(self, i:int) -> int:\n        assert((self.N+i) < len(self.nodes))\n        return self.nodes[self.N+i]\n    \n    def queryMaxAll(self):\n        return self.nodes[1]\n    \n    def queryMaxLeft(self, i:int) -> int:\n        \'\'\'\n        Return the max score saved in range of [0,i] inclusive\n        \'\'\'\n        curr = self.N+i\n        result = self.nodes[curr]\n        path = []\n        while curr > 1:\n            parent = curr >> 1\n            path.append((parent,curr&1))\n            curr = parent\n\n        while path:\n            curr,odd = path.pop()\n            if odd:\n                # when we are going for right child\n                # take best result from left\n                left = curr<<1\n                result = max(result, self.nodes[left])\n            else:\n                # when we are going for left chld, we cannot take memo\n                pass\n        return result\n    \n    def queryMax(self, givenLeft, givenRight, defaultVal = None):\n        \'\'\'\n        Return the maximum value between beg and end\n        \'\'\'\n        assert(givenLeft <= givenRight)\n        assert((self.N+givenRight) < len(self.nodes))\n        \n        ret = max(self.nodes[self.N+givenLeft],self.nodes[self.N+givenRight])\n        if defaultVal is not None:\n            ret = max((defaultVal,-1),ret)\n        stack = [1]\n        while stack:\n            cur = stack.pop()\n            for child in (cur<<1,(cur<<1)+1):\n                rightMost = self.rightMost[child]\n                if rightMost < (self.N+givenLeft):\n                    continue\n                leftMost = self.leftMost[child]\n                if leftMost > (self.N+givenRight):\n                    continue\n\n                if rightMost <= (self.N+givenRight) and leftMost >= (self.N+givenLeft):\n                    ret = max(ret,self.nodes[child])\n                    continue\n                    \n                if defaultVal is not None and self.nodes[child][0] <= defaultVal:\n                    continue\n\n                stack.append(child)\n                \n        return ret\n\n    def printNodes(self, beg,end):\n        print(self.nodes[self.N+beg:self.N+end])\n\nclass PrefixTrie:\n    def __init__(self, val, rk = None):\n        self.val = val\n        self.children = [None]*26\n        if rk is None:\n            self.rk = RKHash()\n        else:\n            self.rk = rk.copy()\n        if val is not None:\n            self.rk.append(val)\n\n    def __getitem__(self, i):\n        return self.children[i]\n\n    def __setitem__(self, i, val):\n        self.children[i] = val\n\n    def add(self, given):\n        cur = self\n        ORDA = ord(\'a\')\n        for x in given:\n            xval = ord(x)-ORDA\n            if cur[xval] is None:\n                cur[xval] = PrefixTrie(xval, cur.rk)\n            cur = cur[xval]\n\n    def find(self, given, beg):\n        cur = self\n        ORDA = ord(\'a\')\n        gn = len(given)\n        for i in range(beg,gn):\n            xval = ord(given[i])-ORDA\n            if cur[xval] is None:\n                return\n            yield i+1,cur[xval].rk\n            cur = cur[xval]\n\n    def getHashes(self, output):\n        assert( (self.rk.val,self.rk.sz) not in output)\n        output[(self.rk.val,self.rk.sz)] = self\n        for x in self.children:\n            if x is not None:\n                x.getHashes(output)\n        \ndef strToAscii(given):\n    ORDA = ord(\'a\')\n    ret = []\n    for x in given:\n        xval = ord(x)-ORDA\n        ret.append(xval)\n    return ret\n\nclass Solution:\n    def minValidStrings(self, words: List[str], givenTarget: str) -> int:\n        N = len(givenTarget)\n        target = strToAscii(givenTarget)\n\n        lookup = set()\n        for w in words:\n            rk = RKHash()\n            wi = strToAscii(w)\n            for x in wi:\n                rk.append(x)\n                lookup.add(rk.key())\n            \n        INF = float(\'Inf\')\n        NINF = float(\'-Inf\')\n\n        subLookup = RKSubstringHash(target)\n\n        def possible(beg,end):\n            assert(beg<end)\n            #subLookup.test_substring(target, beg, end)\n            hcode = subLookup.substring(beg,end)\n            if hcode in lookup:\n                return True\n            return False\n\n        memo = SegmentTreeRMQ(N+2,NINF)\n        memo[N] = 0\n        prevHash = RKHash()\n        prevHash.test()\n        ORDA = ord(\'a\')\n        for pos in range(len(target)-1,-1,-1):\n\n            lo = pos\n            hi = len(target)-1\n            while lo<hi:\n                mid = (lo+hi)>>1\n                if not possible(pos,mid+1):\n                    hi = mid-1\n                else:\n                    if mid == lo:\n                        break\n                    lo = mid\n            # found best match in \n            if hi >= pos:\n                if possible(pos,hi+1):\n                    lo = hi\n            lo = max(lo,pos)\n            if not possible(pos,lo+1):\n                continue\n            #print(pos, \'best match\', givenTarget[pos:lo+1])\n            # longest possible prefix match is at lo\n            # find the minimum value in range pos and lo\n            if lo == pos: # single character match\n                memo[pos] = memo[pos+1][0]-1\n                continue\n            loc = memo.queryMax(pos+1,lo+1)\n            #memo.printNodes(0,N+1)\n            #print(pos+1,lo+1, \'queryMax\', loc)\n            if loc[1] != -1:\n                memo[pos] = loc[0]-1\n\n        memo.printNodes(0,N+1)\n        result = memo[0]\n        result = -result[0]\n        if result > N:\n            return -1\n        return result\n```
['Binary Search', 'Dynamic Programming', 'Segment Tree', 'Rolling Hash', 'Python3']