KMP 알고리즘

많은 코드를 보았지만, blog.naver.com/PostView.nhn?blogId=kks227&logNo=220917078260&categoryNo=299&parentCategoryNo=0&viewDate=&currentPage=4&postListTopCurrentPage=&from=menu&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=4 이 글을 읽고 이해했습니다. 저는 간략하게 설명하지만, 더 자세한 설명이 필요하신 분은 이 글을 참고하시면 될 것 같습니다.

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220917078260&categoryNo=299&parentCategoryNo=0&viewDate=&currentPage=4&postListTopCurrentPage=&from=menu&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=4

문자열 H,S(H>S) 에서 S와 H에 매칭된 부분의  접미사와 접두사가 일치할 시, 그곳부터 탐색하고, 일치하는 부분이 없을시 새로 시작한다는 알고리즘입니다.

    def computeLPS(pat, lps):
        leng = 0  # length of the previous longest prefix suffix
        # 항상 lps[0] ==0 이므로 while 문은 i ==1 부터 시작한다.
        i = 1
        while i < len(pat):
            # 이전 인덱스에서 같았다면, 다음 인덱스만 비교하면 된다.
            if pat[i] == pat[leng]:
                leng += 1
                lps[i] = leng
                i += 1
            else:
                # 일치하지 않는 경우
                if leng != 0:
                    # 이전 인덱스에서는 같았으므로, leng 을 줄여서 다시 검사한다,
                    leng = lps[leng - 1]
                    # 다시 검사해야하므호 i는 증가하지 않는다.
                else:
                    # 이전 인덱스에서도 같지 않았다면, lps[i]는 0이고, i는 1 증가
                    lps[i] = 0
                    i += 1


    def KMPSearch(pat, txt):
        M = len(pat)
        N = len(txt)
        lps = [0] * M
        # preprocess the pattern and
        computeLPS(pat, lps)
        i = 0  # index for txt[]
        j = 0  # index for pat[]
        while i < N:
            # 문자열이 같은 경우, 양쪽 인덱스를 모두 증가시킨다.
            if pat[j] == txt[i]:
                i += 1
                j += 1
            # pattern을 찾지 못한 경우
            elif pat[j] != txt[i]:
                # j!=0 인 경우 짧은 lps에 대한 재검사
                if j != 0:
                    j = lps[i - 1]
                # j==0 이면 일치하는 부분이 없으므로 인덱스 증가
                else:
                    i += 1
            # pattern을 찾은 경우
            if j == M:
                print("Found pattern at index " + str(i - j))
                # 이전 인덱스의 lps 값을 참조해 계속 검색
                j = lps[j - 1]

참고 코드: https://devbull.xyz/python-kmp-algorijeumeuro-munjayeol-cajgi/

참고 문헌

https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220917078260&categoryNo=299&parentCategoryNo=0&viewDate=&currentPage=4&postListTopCurrentPage=&from=menu&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=4