BOJ 1786 찾기

 

이 문제는 처음 봤을 때 그냥 간단한 문자열 비교 문제인가 했다. 하지만 범위가 100만 이하라는 것을 보고 다른 알고리즘의 필요성을 느껴 관련한 알고리즘을 찾아봤다.

 

그런데 이게 왠걸? 이전에 한번 구현하려다 실패한 KMP알고리즘을 쓰는 것이 아니겠는가. 

예전에 클래스 3에 있는 실딱이 문제를 풀다가 특정 문자열을 찾는 위와 비슷한 문제를 풀려고 한 적이 있었다. 그 떄 KMP알고리즘에 대해 한번 접한 적이 있었다. 하지만 그 땐 알고리즘에 대한 경험도 적었고 무엇보다도 위 알고리즘에 사용되는 LPS라는 알고리즘이 전혀 이해가 가질 않아 구현 중 포기했던 문제였다.

 

하지만 진화를 거둔 지금, 다시 한번 이 알고리즘에 도전해보았다.

 

아이디어는 간단하다. 문자열 매칭을 시키면서 겹치는 부분이 만약에 발생을 하면 (이 겹치는 부분은 검사하는 문자열 중에서도 반복되는 부분이다.) 한칸씩 옮겨서 이미 스캔한 곳을 또 스캔하는 것이 아닌 겹치는 곳으로 뿅 하고 점프뛰어서 그 시간을 획기적으로 줄인다는 것이 KMP 알고리즘의 주된 아이디어이다.

 

하지만 여기서 어려운 것은 이 반복되는 부분을 찾는것이다. 그래서 이에 대해서 이해하느라 거진 하루를 썼다.

이 반복되는 부분을 찾는 것을  LPS라고 한다. 이것은 약간 투포인터 느낌으로 입력된 문자열을 스캔한 뒤 어느 인덱스에서 얼마나 반복되는지를 미리 저장해서 써먹는 알고리즘이다.

이 알고리즘을 간단히 설명하자면 인덱스 i랑 j가 있는데 i는 하나씩 증가하면서 문자열을 전부 검사하는 포인터, j는 겹치는걸 가르키는 포인터이다. 그리고 이 포인터들을 잘 조작해서 겹치는 부분을 판단한 뒤 배열에 넣어 반환하는 알고리즘이다.

일단 LPS는 i가 0일때 무조건적으로 0이므로 i가 1일때부터 검사를 진행한다.  그리고 i번째 문자와 j번째 문자를 비교해서 만약 둘이 같다면, 겹치는 것으로 판단하고 j를 하나 증가시키고 현재의 LPS배열에 증가시킨 j를 저장한다. 

하지만 둘이 같지 않다면, j가 0보다 클 때 (j는 사실상 겹치는 부분의 길이를 나타내는 변수라 봐도 무방함) j를 감소시킨다. 하지만 이 감소시킬 때, 다시한번 LPS배열의 힘을 빌려 지금까지 검사한 문자열 중에서도 겹치는걸 걸러내서 점프한다. (여기가 가장 이해하기 어려웠다. 하지만 차근차근 직접 인덱스를 적어가며 풀이해보니 어느샌가 이해가 갔다. 약간 재귀와 비슷한 느낌이다. 하지만 함수로 재귀를 시키는 것이 아닌 이미 저장된 LPS배열을 통해 만드는 재귀느낌)

이를 i가 len(string) - 1이 될 때 까지, 즉 모든 문자열에 대해서 LPS를 형성할 때 까지 실행해서 LPS배열을 형성한다. 그리고 형성된 LPS배열을 리턴하여 알고리즘을 마친다.

 

이 다음부턴 매우 쉽다. 그냥 인덱스에 조심하면서 LPS배열을 기반으로 검사하고 점프뛰고 뭐시기 하면 어느샌가 모든 인덱스를 구할 수 있다.

 

나는 문제를 대충 읽어서 답의 출력방식을 지키지 않아 몇번 틀리긴 했지만 KMP알고리즘을 제대로 구현만 한다면 쉽게 맞출 수 있는 간단한 문제였다. 

 

 

S = input()
SEARCH = input()

def KMP(allst,scanst):
    def LPS(st):
        lps = [0] * len(st)
        length = 0
        i = 1
        while i < len(st):
            if st[i] == st[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0: length = lps[length-1]
                else:
                    lps[i] = 0
                    i += 1
        return lps
    
    lenAll = len(allst)

    lps = LPS(scanst)
    ret = []
    i = 0
    j = 0

    while i < lenAll:
        if allst[i] == scanst[j]:
            i += 1
            j += 1
            if j == len(scanst):
                ret.append(i - j + 1)
                # print(i - j + 1, end=" ")
                j = lps[j - 1]
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return ret
    
ret = KMP(S,SEARCH)
print(len(ret))
for _ in ret:
    print(_)

 

근데 갑자기 오늘부터 캡쳐도구로 캡쳐를 하면 광도가 엄청 올라간 상태로 캡쳐되는데 왜이러는 건가요? 

모니터엔 정상적으로 보이는데 캡쳐도구로 캡쳐만 하면 이렇게 되네요... 

혹시 해결 방법 아시는 분 댓글 남겨주시면 감사하겠습니다 :)