Remove all occurrences of a word from a given string using Z | Function to fill the Z - array for str ; L Stores start index of window which matches with prefix of str ; R Stores end index of window which matches with prefix of str ; Iterate over the characters of str ; If i is greater thn R ; Update L and R ; If substring match with prefix ; Update R ; Update Z [ i ] ; Update R ; Update k ; if Z [ k ] is less than remaining interval ; Update Z [ i ] ; Start from R and check manually ; Update R ; Update Z [ i ] ; Update R ; Function to remove all the occurrences of word from str ; Create concatenated string " P $ T " ; Store Z array of concat ; Stores string , str by removing all the occurrences of word from str ; Stores length of word ; Traverse the array , Z [ ] ; if Z [ i + pSize + 1 ] equal to length of word ; Update i ; Driver Code
def getZarr ( st , Z ) : NEW_LINE INDENT n = len ( st ) NEW_LINE k = 0 NEW_LINE L = 0 NEW_LINE R = 0 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( i > R ) : NEW_LINE INDENT L = R = i NEW_LINE while ( R < n and st [ R - L ] == st [ R ] ) : NEW_LINE INDENT R += 1 NEW_LINE DEDENT Z [ i ] = R - L NEW_LINE R -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT k = i - L NEW_LINE if ( Z [ k ] < R - i + 1 ) : NEW_LINE INDENT Z [ i ] = Z [ k ] NEW_LINE DEDENT else : NEW_LINE INDENT L = i NEW_LINE while ( R < n and st [ R - L ] == st [ R ] ) : NEW_LINE INDENT R += 1 NEW_LINE DEDENT Z [ i ] = R - L NEW_LINE R -= 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT def goodStr ( st , word ) : NEW_LINE INDENT concat = word + " $ " + st NEW_LINE l = len ( concat ) NEW_LINE Z = [ 0 ] * l NEW_LINE getZarr ( concat , Z ) NEW_LINE res = " " NEW_LINE pSize = len ( word ) NEW_LINE for i in range ( l ) : NEW_LINE INDENT if ( i + pSize < l - 1 and Z [ i + pSize + 1 ] == pSize ) : NEW_LINE INDENT i += pSize - 1 NEW_LINE DEDENT elif ( i < len ( st ) ) : NEW_LINE INDENT res += st [ i ] NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " Z - kmalgorithmkmiskmkmkmhelpfulkminkmsearching " NEW_LINE word = " km " NEW_LINE print ( goodStr ( st , word ) ) NEW_LINE DEDENT