def KMPPrefixTable(oldP):
    m=len(oldP)
    P = " "+oldP 
    pi =  [0] * (m+1)
    k=0
    for q in range(2,m+1):
        while (k>0 and P[k+1] != P[q]):
            k=pi[q]
        if (P[k+1] == P[q]):
            k=k+1
        pi[q] = k
    return pi
            
pi = KMPPrefixTable("abacab")
print(pi[1:])

def KMP_match(T, P):
    """
    Inputs: T -Text string and P - Pattern string
    Returns: Prints the indices where the pattern is found in the text.
    """
    pi = KMPPrefixTable(P)
    print(pi)
    n = len(T)
    m = len(P)
    T=" "+T
    P=" "+P
    q=0
    matches = []
    for i in range(1,n+1):
        while (q>0 and P[q+1] != T[i]):
            q = pi[q]
        if (P[q+1] == T[i]):
            q=q+1
        if (q==m):
            print("Pattern found with shift ", i-m)
            print(T[i-m:i+1])
            q=pi[q]
text = """The world is changing exponentially and so are we. 
Cambridge Institute of Technology, Karnataka have always been in the forefront 
among providers of quality education in Karnataka and leaders in 
transforming more than 15000 lives. Meeting the fast pace of 
global change, CIT is accelerating the transformation within 
the institution to make a better innovative world. 
"""
pattern = "the"
KMP_match(text, pattern)
