백준 1701번

접근 방식(알고리즘 분류)

• KMP

내 풀이

# 일치하는 부분 문자열의 최대 길이를 기록하는 테이블 생성
def make_table(s):
    table = [0 for _ in range(len(s))]
    j = 0
    for i in range(1, len(s)):
        #같을때까지 j를 뒤로 건너뛰면서 후퇴
        while j > 0 and s[j] != s[i]:
            j = table[j-1]
        #같아집면 table에 j+1값을 대입 --> i, j 둘다 1씩 증가
        if s[j] == s[i]:
            table[i] = j + 1
            j += 1

    return max(table)

s = input()

result = 0
for i in range(len(s)):
    result = max(result, make_table(s[i:len(s)]))

print(result)

풀이 설명

이 문제 같은 경우는 KMP알고리즘에서 적용되는 Failure 배열 을 구현할 줄 알면 해결할 수 있는 문제였다.