BOJ-1786 - Python

문자열 t 안에 문자열 p가 몇개 들어있는 지, 시작하는 인덱스는 어디인 지 출력하는 문제. 단순히 모든 문자열을 비교할 시 O(len(t)*len(p))가 되어 길이가 길어질 시 기하급수적으로 커지게 된다. 이를 해소하고자 KMP 방식을 공부 및 적용하여 풀었는데, p에 대한 LPS(최장길이 접미사 and 접두사)를 저장하여 문자열 비교간에 LPS를 이용하여 p에 대한 인덱스 값을 수정하여 비교를 줄이는 방식이며 시간복잡도는 O(len(t)+len(p))이다. 자세한 설명은 주석을 참고.

def KMP(t, p):
    lt = len(t)
    lp = len(p)
    lps = [0 for _ in range(lp)]
    findLPS(p, lps)

    ans = 0; ans_l = [] # 일치하는 수와 일치하는 곳의 index를 저장할 변수

    i = 0 # 텍스트와 비교할 변수
    j = 0 # 패턴과 비교할 변수
    while i < lt:
        if t[i] == p[j]:
            # 문자가 같을 시 i와 j 둘 다 상승
            i += 1
            j += 1
        elif t[i] != p[j]:
            # 같지 않지만
            if j != 0:
                # 전에 문자가 같았을 시
                # lps를 이용하여 j의 값을 수정 후 재비교
                j = lps[j-1]
            else:
                # 전에 문자가 같지 않았을 시 index 이동
                i += 1

        if j == lp: # 패턴의 끝까지 동일 시
            # 정답을 위한 변수 수정
            ans += 1
            ans_l.append(i - lp + 1)
            # lps를 이용하여 j의 값을 수정 후 재비교
            j = lps[j-1]

    return ans, ans_l

def findLPS(p, lps):
    # 패턴을 이용하여 LPS( Longest proper prefix which is suffix, 접두사 이자 접미사의 최장길이 )
    # 를 찾음

    leng = 0
    i = 1
    while i < len(p):
        # 문자가 같을 시
        if p[i] == p[leng]:
            # 길이를 늘린 후 lsp 배열에 저장한 후 다음 인덱스로 넘어감
            leng += 1
            lps[i] = leng
            i += 1
        # 문자가 같지 않을 시
        else:
            if leng != 0:
                # 전에 같았으면
                # 해당 길이로 변경 후 재 비교
                leng = lps[leng-1]
            else:
                # 전에도 같지 않을 시
                # lps의 값을 0으로 저장 후 index 이동
                lps[i] = 0
                i += 1

t = input()
p = input() # 찾아야 할 패턴
ans, ans_l = KMP(t, p)
print(ans)
print(*ans_l)

Written by@hyesungoh
Learning every moment

InstagramGitHubLinkedIn