[Algorithm] Brute Force Method

def bf_match(txt:str, pat:str)->int:
    pt=0
    pp=0
    #일단 텍스트를 따라가는 pt와
    #패턴을 따라가는 pp 를 0으로 초기화 했습니다.
    while pt!=len(txt) and pp!=len(pat):
        #그리고 pt가 텍스트크기를 다 탐색하거나
        #패턴커서가 패턴의 크기를 다 탐색했을경우
        #while문을 종료합니다.
        if txt[pt]==pat[pp]:
            pt+=1
            pp+=1
            #만약 텍스트커서와 패턴에 있는 커서를 비교해서
            #둘이 일치할경우 커서를 이동해도 문제가 없다!
            #그리고 다음 비교를 수행합니다.
        else:
            pt=pt-pp+1
            pp=0
            #일치하지 않을 경우에는
            #여기서는 텍스트나 패턴의 문자를 다 탐색하지 않을경우니까
            #                   패턴 문자열이 탐색이 다 되지 않을 경우
            #                   이 경우는 중간에 다르다는 판별을 받았으므로
            #                   패턴이 커서가 0으로 초기화가 되었고
            #                   텍스트를 따라가는 커서는 패턴과 맞았던 위치까지만 빼주고 +1 하면
            #                   재탐색할 문자 인덱스를 줍니다. 그러면 텍스트 커서는 거기에 위치하고
            #                   pp는 다시 0으로 되어서 그 텍스트커서부터 같이 카운트하며 비교합니다.
    return pt - pp if pp==len(pat) else -1
            #그래서 pp가 패턴탐색을 다했을 때는 찾았다는 뜻이니까
            #pp와 같이 최대 끝까지 탐색된 pt는 그 최대 pt에서 pp를 빼주게 되면 그 인덱스가 나옵니다.
            #ex) 0 1 2 3 4 5 6 7 <- pt
            #                           0 1 2<-pp
            #7-2=5   이런식으로


if __name__=='__main__':
    s1=input('텍스트를 입력하세요.: ')
    s2=input('패턴을 입력하세요.: ')

    idx=bf_match(s1, s2)
    if idx==-1:#위에서 못찾았을때 -1 리턴
        print('텍스트 안에 패턴이 존재하지 않습니다.')
    else:
        print(f'{(idx + 1)}번째 문자에서 일치합니다.')

브루트 포스는 인덱스를 거쳐가면서 한 회차에서 맞지 않는 패턴을 발견시 다시 패턴인덱스를 0으로 초기화 한 후에

해당변수[pt]를 적절하게 이동시키면서 다시 비교하는 알고리즘 입니다.

 

참고 : 자료구조와 함께 배우는 알고리즘 입문 브루트 포스편