finding where a string is present in text

stringPatternMatching.py

'''https://www.coursera.org/learn/algorithms-on-strings'''


def computePrefixFunction(pattern):
    '''returns a list containing longest border for each char from the first character in the pattern.
    for example, for string abcab, it would return [0, 0, 0, 1, 2]

    Border of a string: prefix of the string == suffix of the string
    Example: ab is the border of string abcbab since ab is the prefix as well as suffix of that string'''

    prefixArray = []
    prefixArray.append(0)
    border = 0

    for i in range(1, len(pattern)):

        while (border > 0) and (pattern[i] != pattern[border]):
            border = prefixArray[border-1]

        if pattern[i] == pattern[border]:
            border += 1
        else:
            border = 0

        prefixArray.append(border)

    return prefixArray




def knuthMorrisPrattAlgorithmToFindAllOccurrences(pattern, text):
    '''finds the indices of occurrences of pattern in the text'''

    string = pattern + '$' + text
    prefixArray = computePrefixFunction(string)

    indicesOfOccurrencesList = []

    lengthOfPattern = len(pattern)
    for i in range(lengthOfPattern+1, len(string)):
        if prefixArray[i] == lengthOfPattern:
            indicesOfOccurrencesList.append(i - (2*lengthOfPattern))

    return indicesOfOccurrencesList






if __name__ == '__main__':

    indicesOfOccurrencesList = knuthMorrisPrattAlgorithmToFindAllOccurrences('abra', 'abracadabra')
    print('\nIndices Of Occurrences of abra in abracadabra:', indicesOfOccurrencesList)