def getnext(pattern):
    m = len(pattern)
    i = 1
    j = 0
    next = [0] * (m+1)
    while i < m:
        if pattern[i] == pattern[j]:
            i += 1
            j += 1
            next[i] = j
        elif j == 0:
            i += 1
            next[i] = j
        else:
            j = next[j]
    return next

def kmp(text, pattern):
    next = getnext(pattern)
    i = j = 0
    n = len(text)
    m = len(pattern)
    while i < n and j < m :
        print i, text[i], j, pattern[j]
        if text[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = next[j]
    if j == m:
        return i - j
    return -1

text = 'ABCABCABA'
pat  = 'ABCABA'
print getnext(pat)
print kmp(text, pat)