def make_kmp_table(pattern,border):
    
    m= len(pattern)
    border[0= -1
    border[1= 0
    
    i = 2
    cnd = 0
    
    while(i < m):
        if pattern[i-1== pattern[cnd]:
            cnd += 1
            border[i] = cnd
            i += 1
            
        elif cnd > 0:
            cnd = border[cnd]
            
        else:
            border[i] = 0
            i += 1
 
def kmp_search(pattern, border, text):
    index = []
    m = 0
    i = 0
    t_len = len(text)
    p_len = len(pattern)
    
    while m+< t_len:
        if pattern[i] == text[m+i]:
            if i == p_len-1:
                index.append(m)
                i = 0
                m += 1
            i += 1
        else:
            if border[i] > -1:
                m = m + i- border[i]
                i = border[i]
            else:
                i = 0
                m += 1
    return index
 
if __name__=='__main__':
    pattern = input("Please input the pattern : ")
    print('\n')
    border = []
    leng = len(pattern)
    index_key = 0
    for i in range(len(pattern)):
        border.append(0)
    make_kmp_table(pattern,border)
    with open('source.txt') as f:
        line_number = 1       
        for line in f:
            cols = list(line)
            index = kmp_search(pattern,border,cols)
            if index:
                for index_target in index:
                    index_target = index_target + index_key
                    cols.insert(index_target,'[[')
                    cols.insert(index_target+leng+1,']]')
                    index_key += 2
                index_key = 0
                print(line_number,index,"------")
                for k in cols:
                    print(k,end='')
                print('\n')
            line_number += 1

cs


+ Recent posts