def BuildGST(pattern, suffix, GST):
    m = len(pattern)
    suffix[m-1= m
    g = m-1
    
    for i in range(m-2-1-1):
        if i > g and suffix[i+m-1-f] < i-g:
            suffix[i] = suffix[i+m-1-f]
        else:
            if i < g:
                g = i
            f = i
            while (g>=0 and pattern[g]==pattern[g+m-1-f]):
                g-=1
            suffix[i] = f-g
            
        for i in range(0,m,1):
            GST[i] = m
            
        j=0
        for i in range(m-1-1-1):
            if suffix[i] == i+1:
                while(j < m-1-i):
                    if GST[j] == m:
                        GST[j] = m-1-i
                    j+=1
        for i in range(0,m-1,1):
            GST[m-1-suffix[i]] = m-1-i
            
def BuildBCT(pattern,BCT):
    
    for i in range(10000):
        BCT.append(-1)
    for i in range(len(pattern)):
        BCT[ord(pattern[i])] = i
 
 
def search(pattern,GST,BCT,text):
    index = []
    m = 0
    t_len = len(text)
    p_len = len(pattern)
    i = p_len - 1
    
    while m+< t_len:
        if pattern[i] == text[m+i]:
            if i == 0:
                index.append(m)
                i = p_len-1
                m += 1
            i -= 1
        else:
            m = m + max(GST[i], i-BCT[ord(pattern[i])])
            i = p_len-1
    return index
if __name__=='__main__':
    pattern = input("Please input the pattern : ")
    print('\n')
    GST = []
    BCT = []
    suffix = []
    leng = len(pattern)
    index_key = 0
    for i in range(len(pattern)):
        GST.append(0)
        BCT.append(0)
        suffix.append(0)
    BuildGST(pattern, suffix, GST)
    BuildBCT(pattern,BCT)
    with open('source.txt') as f:
        line_number = 1       
        for line in f:
            cols = list(line)
            index = search(pattern,GST,BCT,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
 
    
              




+ Recent posts