# Python program for KMP Algorithm
from time import time


def KMPSearch(pat, txt):
    M = len(pat)
    N = len(txt)
    # create lps[] that will hold the longest prefix suffix
    # values for pattern
    lps = [0]*M
    j = 0  # index for pat[]
    # Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps)
    i = 0  # index for txt[]
    loop_counter = 0
    while i < N:
        loop_counter += 1
        if pat[j] == txt[i]:
            i += 1
            j += 1

        if j == M:
            print("Found pattern at index " + str(i-j))
            j = lps[j-1]
        # mismatch after j matches
        elif i < N and pat[j] != txt[i]:
            # Do not match lps[0..lps[j-1]] characters,
            # they will match anyway
            if j != 0:
                j = lps[j-1]
            else:
                i += 1
    print('Loop counter for complete algo is: {}'.format(loop_counter))


def computeLPSArray(pat, M, lps):
    len = 0  # length of the previous longest prefix suffix
    lps[0]  # lps[0] is always 0
    i = 1
    # the loop calculates lps[i] for i = 1 to M-1
    loop_counter = 0
    while i < M:
        loop_counter += 1
        if pat[i] == pat[len]:
            len += 1
            lps[i] = len
            i += 1
        else:
            # This is tricky. Consider the example.
            # AAACAAAA and i = 7. The idea is similar
            # to search step.
            if len != 0:
                len = lps[len-1]

                # Also, note that we do not increment i here
            else:
                lps[i] = 0
                i += 1
    print('loop_counter for computeLPSArray is: {}'.format(loop_counter))


def search(pat, txt):
    M = len(pat)
    N = len(txt)
    loop_counter = 0
    # A loop to slide pat[] one by one */
    for i in range(N - M + 1):
        j = 0

        # For current index i, check
        # for pattern match */
        while(j < M):
            loop_counter += 1
            if (txt[i + j] != pat[j]):
                break
            j += 1

        if (j == M):
            print("Pattern found at index ", i)
    print('In brute force, number of iterations were {}'.format(loop_counter))


txt = "gcagtacgcagagagtatacagtacg"
pat = "agtacg"
KMPSearch(pat, txt)
print(len(txt))
print(len(pat))

print('applying brute force')
search(pat, txt)