[백준/약점체크] 16916번: 부분문자열

[문제]

링크: https://www.acmicpc.net/problem/16916

 

[내 코드]

 

문제를 해결하기 위해서 KMP 알고리즘을 공부하고 구현했다. 자세한 내용은 이 글을 참고.

def LPS(pat, lps):
    leng = 0
    i = 1
    while i < len(pat):
        if pat[i] == pat[leng]:
            leng += 1
            lps[i] = leng
            i += 1
        else:
            if leng == 0:
                lps[i] = 0
                i += 1
            else:
                leng = lps[leng-1]
                
def KMP(txt, pat):
    N = len(txt)
    M = len(pat)
    
    lps = [0] * M
    LPS(pat, lps)
    i = j = 0
    while i < N:
        if pat[j] == txt[i]:
            j += 1
            i += 1
        else:
            if j == 0:
                i += 1
            else:
                j = lps[j-1]
        if j == M:
            # 마저 검색하기 원한다면 return으로 while문을 끊으면 안 된다
            # j = lps[j-1] 로 돌아가 계속 검색할 수 있다
            return 1
    return 0

txt = input().rstrip()
pat = input().rstrip()

print(KMP(txt, pat))

 

검색 알고리즘을 구현하지 않고 파이썬 내장 기능을 써도 통과는 됨

N = input()
M = input()

print(int(M in N))

 

삽질의 흔적.. 범인은 잘못 쓴 알파벳 하나였다 ;_;

 

 

[개선안]

# 부분 문자열
P, S = input().strip(), input().strip()


def get_table(x):
    arr = [0 for _ in range(len(x))]
    j = 0
    for i in range(1, len(x)):
        while j > 0 and x[i] != x[j]:
            j = arr[j-1]
        if x[i] == x[j]:
            j += 1
            arr[i] = j
    return arr


def kmp(word, find):
    result = 0
    j = 0
    for i in range(len(word)):
        while j > 0 and word[i] != find[j]:
            j = table[j-1]
        if word[i] == find[j]:
            if j == len(find)-1:
                result += 1
                j = table[j]
            else:
                j += 1
    return result


table = get_table(S)
result = kmp(P, S)
print(1 if result else 0)

나는 KMP알고리즘을 공부하면서 구현한 코드를 변형해서 제출했는데, 인터넷에서 흔히 보이는 정답은 좀 다르게 생겼다

- LPS 를 구할 때 : leng 대신에 j를 썼다. (j가 0보다 크며 비교하는 두 문자가 일치하지 않을 때)를 조건으로 반복문을 넣어주었다. j 앞 인덱스의 lps값으로 j를 대체하기를 반복한다. j가 0이 되거나 두 문자가 일치하면 반복문에서 벗어난다. 

- (j가 0보다 크며 비교하는 두 문자가 일치하지 않을 때) : "지금은 다르지만 앞 부분문자열에서 lps가 있었다" -> 그 이전 lps값 기준으로 재검사

- KMP를 구할 때: i, j 포인터로 각 문자열을 검사하는 건 같다. 패턴의 첫번째 단어가 아닌데 문자가 일치하지 않으면 lps 기준으로 j 위치를 다시 세팅한다. (그 전까지는 일치했다는 의미이므로)

- j가 문자열의 마지막 인덱스에 가 닿으면 result에 1을 더해준다. (문자열이 반복되는 횟수만큼 쌓임)

- 그리고  j = table[j]의 의미.. 비교하는 두 문자가 같지 않을 때는 '그 문자의 앞' LPS값을 썼는데, 이 경우에는 마지막 인덱스까지 가서 일치했다는 의미니까 '바로 그 자리의' LPS 값을 써서 검사를 재개하면 된다. 아래 그림 참고!

마지막 문자가 일치했으니, 그 문자의 LPS 만큼 당겨주고 시작한다!

 

*KMP 알고리즘 글에도 썼지만, 
LPS 값을 이렇게 기억하는 게 편하다 : 동일한 접두사-접미사의 최대 '길이'이니까, LPS값이 인덱스로 사용될 때는 '접두사가 끝난 그 다음 문자'를 가리키게 된다.

 

예를 들어, txt = 'ABCXABC' 의 LPS는 'ABC'로 3이다. 

이 LPS 값으로 텍스트를 인덱싱하면, txt[3] = X, 즉 'ABC'가 끝난 그 다음 문자 'X'다.

 

j=lps[j-1] 이런 식으로 다시 세팅하는 것도, 접두사를 생략하고 그 다음 문자부터 비교를 시작하겠다는 의미인 것이다!