"""
You have two arrays of strings, words and parts. Return an array that contains the strings from words,
modified so that any occurrences of the substrings from parts are surrounded by square brackets [],
following these guidelines:

If several parts substrings occur in one string in words, choose the longest one. If there is still
more than one such part, then choose the one that appears first in the string.

For words = ["Apple", "Melon", "Orange", "Watermelon"] and parts = ["a", "mel", "lon", "el", "An"],
the output should be:

findSubstrings(words, parts) = ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"].

"""

def failure(pattern):
    matchCount = 0
    d = set()
    indices = [0] * len(pattern)
    for i in range(len(pattern)):
        if pattern[i] in d:
            matchCount += 1
        else:
            matchCount = 0
            d.add(pattern[i])
        indices[i] = matchCount
    return indices


def KMP(text, pattern):
    failureIndices = failure(pattern)
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]: # character match
            if j == len(pattern)-1:
                return i-len(pattern)+1 # complete match
            i += 1
            j += 1
        elif j > 0: # no match but we have advanced through pattern
            j = failureIndices[j-1]
        else: # no match and have not advanced through pattern
            i += 1
    return -1 # no match exists


def findSubstrings(words, parts):
    for i in range(len(words)):
        length = -1
        partLocation = -1
        wordIndex = -1
        for j in range(len(parts)):
            index = KMP(words[i], parts[j])
            if index is not -1 and len(parts[j]) > length:
                length = len(parts[j])
                partLocation = j
                wordIndex = index
            # elif is for finding first occurrence when we have equal length answers
            elif index is not -1 and len(parts[j]) == length:
                if index < wordIndex:
                    length = len(parts[j])
                    partLocation = j
                    wordIndex = index
        if partLocation is not -1:
            words[i] = words[i][:wordIndex] + "[" + words[i][wordIndex:wordIndex+length] + "]" + words[i][wordIndex+length:]
    return words


words = ["neuroses", "myopic", "sufficient", "televise", "coccidiosis", "gules", "during", "construe", "establish", "ethyl"]
parts = ["aaaaa",  "Aaaa", "E",  "z",  "Zzzzz", "a", "mel", "lon", "el",  "An",  "ise", "d", "g","wnoVV", "i", "IUMc", "P", "KQ", "QfRz", "Xyj", "yiHS"]
print(findSubstrings(words, parts))