[Algorithm] KMP

Programming/Algorithm 2020. 11. 23. 06:34

def kmp_match(txt:str,pat:str)->int:
    #txt는 원본 텍스트를 말하며 pat는 비교되어지는 패턴을 말합니다.
    """KMP법으로 문자열 검색하기"""
    pt=1                                            #txt를 따라가는 커서
    pp=0                                            #패턴을 따라가는 커서
    skip=[0]*(len(pat)+1)
    ###########과제 : length 길이에 왜 +1 인지?
    # ABCABD를 예로 들었을 때
    # 이 소스코드에서는 TXT가 1부터 시작할 때 PP 0과 1의 값을 먼저 비교하며
    # 건너 뛰기 테이블에 인덱스를 TXT와 같이 쓰기 위해서 씁니다.
    # 즉 TXT (PT)와 0부터 비교하지않고 SKIP과 인덱스를 맞추려니
    # PT의 값도 +를 먼저 해주기 때문에 마지막으로 가면 인덱스가 6을 커서해서
    # SKIP의 6 인덱스를 건들고나서 후위 판별로 WHILE이 끝나게 됩니다.
    # 그래서 SKIP[1]을 0으로 준이유가 인덱스 0과 1을 비교했을 때 PT가 +1이 되고 나서야
    # 0인 PP를 그 SKIP[2]에 0과 1을 비교한 결과를 저장해서 결국 SKIP [1]은 교과 DATA를 기준으로 한다면
    # 접두사 접미사 비교 방식에 A와 A를 비교한결과라 비교하지 못하는 단독 A에 대해서는 0을 줍니다.
    # ######################################################################
    #이 소스코드에서는 pt는 +를 해주고 그에 맞는 값을 스킵에 후에 넣어주기 때문입니다.
    #만약 첫번째 값을 비교하는 순서를 넣어주면 len 값도 +1없이 0부터 쓸 수 있습니다
    #
    #이 소스코드에서는 불필요한 첫번째 비교 연산을 줄여주려고 한것 같습니다.
    ########################################################################
    # ABCABD를 예로 들자
    # 건너뛰기 표를 만드는 곳
    skip[pt]=0
    while pt!=len(pat):
        # pt의 값은 알고리즘 특성상 마이너스없이 계속가기 때문에
        # len(pat)값이 되면 그만둡니다.
        # 실질적으로 0,1,2,3,4,5 를 해주고 값 6이 되면 끝냅니다.
        # pt의 초기 값은 1과 pp는 0이다.
        # 이 말은 즉슨 처음 패턴의 pp와 pt를 0과 1인덱스를 비교한다.
        if pat[pt]==pat[pp]:
            pt+=1
            pp+=1
            skip[pt]=pp
            # 만약에 pt값과 pp가 맞으면 건너뛰기에 pt인덱스에 하나가 맞으면 pp값이 +되었다(같으니까)
            # -> 문자열중에 하나가 같으니까 그 PT인덱스+1에 (스킵에 포커스)에 1(pp가 +된 값)을 넣어줍니다.
            # -> 문자열중에 넘어가서 연속으로 2개가 맞으면 pp는 2가되며 이것을 pt+1인덱스에(스킵에 pt 포커스)넣어주면
            # ->2가 연속으로 두개가 맞았다는 것을 의미
            # 0,1이 맞아서 또 넘어가면 1(PP),2(PT) 가 될것이니까 당연히 SKIP[pt+1]에 들어가는 원리
        elif pp==0:
            pt+=1
            skip[pt]=pp
            # 여기서 첫번째 IF를 거쳐서 같지않다면!!!!!!!!!!!!!!!!<이것을 주의해야됨
            # 같지 않을때 이 ELIF로 오기때문에 같지않으면 SKIP 알맞은 인덱스에 0이 들어가야됨.

            # 해당 1이든 2든 3이든 처음 인덱스 a(PP=0)와 같지 않지만 a 즉 처음이면
            # pt만 +1을 해줌으로써 비교 당하는 인덱스를 0과 다음 pt+1을 비교함
            # ->이유는 당연히 처음 인덱스와 그 인덱스가 안맞았으니
            # ->처음 인덱스와 그의 다음인덱스(만약 계속 맞지 않다면 0과 pt+len(pat)까지 갈 것이다.)
            # ->를 비교해야 합니다.
            # ->그리고 건너뛰기표에 해당 인덱스는 하나도 맞지 않았다는 표시로 (PP=0)0을 집어넣습니다.
        else:
            pp=skip[pp]
    # 제일 핵심부분

    # 위의 내용까지는 단순 그 자체이다 근데 제일 헷갈렸던것은 여기입니다.
    # 이쪽이 핵심부분인것 같기도 합니다.
    # 근데 계속 봤더니 진짜 정말로 단순합니다.
    # pt        :        0 1 2 3 4 5 6
    # value:         - 0 0 1 2                 #이 부분은 두개가 일치하다는 뜻 즉, 패턴의pt: 3,4인덱스와  pp=0,1인덱스가
    # 맞아떨어졌다는 뜻인데 다음 pt=5 pp=2 (둘다 맞아서 +1씩 된상태)  일때  d와 c는 일치하지 않습니다.
    # 그러면 일치하지 않는 pp의 이전 인덱스인  pp(2)-1 이다.(하지만 아직 조건(일치한다 첫번째 if)가 맞아떨어지지 않아서 1입니다.)
    # pp=1을가지고 건너뛰기 그래프의 pp=1 skip[1]로 가게 되면 그 때 까지는  맞았던 건너뛰기 그래프의 값 0 (개수)만큼 pp로 돌아와서
    # 이전으로 커서를 옮기고 (만약에 1이면 pp의 틀린 부분의 바로 1전인 부분부터 ) 옮겨진 그쪽 pt부터 해당 pt에 pp를 0으로놓고 다시
    # 검사를 시작합니다.

    # 다른 예로 만약 틀린 위치 pp에서 이전 pp인덱스로 skip을 찾아가면 어디서부터 비교를 해야하는지 (다시비교해야할 pp의 값) 를
    # 제공합니다. 그러면 pp를 해당인덱스로 잡아서 틀린위치 pt는 그대로 두고 skip에서 제공받은 인덱스를 pp로 맞춰서 pt와 pp를 비교합니다.

    # 교수님 이거는 제가 과제하면서 kmp알고리즘을 이해하기에 좋아서 일단 기록했습니다.
    # https://www.youtube.com/watch?v=q-SMEUwcnJI               ->part1
    # https://www.youtube.com/watch?v=79F67cXaDUs                ->part2

    #######문자열을 검색하는 란 ########
    pt=pp=0
    while pt!=len(txt)and pp!=len(pat):#검색이니까 둘다 처음부터 비교
        if txt[pt]==pat[pp]: #txt와 pat의 인덱스 문자열이 같으면
            pt+=1
            pp+=1
            # 각각 인덱스를 +1시켜서 다음 문자열을 비교할거다!
        elif pp==0:
            pt+=1
            # 만약에 문자열이 다르고 패턴의 첫번째 값을 txt값과 비교했으면
            # pt에다가 +1을 시켜서 다음 텍스트인덱스에 패턴 첫번째와 같은 값이 있으면
            # 이라는 조건이다.
        else:
            pp=skip[pp]
        # 위에서 설명했던 것 처럼 검색 중 값이 맞지 않을 시에
        # 단, 이 알고리즘 특성상 o(n+m) 이라서 pt는 계속 훑기만 +만 한다.
        # n은 텍스트를 한번 훑는 횟수
        # m은 건너뛰기 표를 만드는 횟수
        # 그래서 검색에 실패할 시에는 매칭에 실패한 위치의 전 pp인덱스를 skip 인덱스로 취해 찾으면
        # 어디서부터 다시 검색하면 될지 pp의 인덱스를 반환합니다.
    return pt-pp if pp==len(pat) else -1
    # len pat를 좇는 pp값이 pat len과 일치한다는 것은 pt -pp를 해주면
    # ex) pt  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    #       pp                                                   12                                <len 이 12이며 pp도 12에 이르렀을 때
    #       pt는 15까지 while조건에 맞춰 다 카운트 했을거고
    #       15 - pp(패턴 len)을 해주면 그 패턴의 시작 인덱스가 나옵니다
if __name__=='__main__':
    s1=input('텍스트를 입력하세요.: ')
    s2=input('패턴을 입력하세요.: ')

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

https://www.youtube.com/watch?v=q-SMEUwcnJI ->part1