백준 문제 링크: https://www.acmicpc.net/problem/1701
문제 요약
문자열에서 두 번 이상 나오는 부분문자열 중 가장 긴 길이 출력
abcabc : 3 abc
ababcabab : 2 ab
핵심 아이디어
KMP에서 사용하는 테이블 만들기 알고리즘을 사용하면 된다.
풀이
# gold3-1701. Cubeditor
import sys
input = sys.stdin.readline
string = input().rstrip()
result = 0
# 매칭이 실패했을 때 얼마나 점프해야하는지를 접두사 접미사가 일치하는 것 기준으로 길이 알려줌.
def make_table(pattern):
table = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
# 따라가다가 j가 i와 다르면 j를 직전으로 돌림(j-1의 테이블 값으로 j를 변경)
while j > 0 and pattern[i] != pattern[j]:
j = table[j - 1]
# i와 j가 가리키는 값이 같으면 숫자 1 증가시켜서 그 다음 문자열까지 같은지 봄
# 일치하면 i와 j 둘다 증가, 아니면 i만 증가
if pattern[i] == pattern[j]:
j += 1
table[i] = j
return table
for i in range(len(string)):
sub_string = string[i:]
result = max(result, max(make_table(sub_string)))
print(result)
실행 시간
메모리 31256KB, 시간 2048ms (python3)
'ALGORITHM > 백준' 카테고리의 다른 글
[BOJ/PYTHON] 1764. 듣보잡 (0) | 2023.07.27 |
---|---|
[BOJ/PYTHON] 16916. 부분 문자열 (0) | 2023.07.27 |
[BOJ/PYTHON] 6996. 애너그램 (0) | 2023.07.27 |
[BOJ/PYTHON] 11003. 최솟값 찾기 (0) | 2023.06.15 |
[BOJ/PYTHON] 4583. 거울상 (0) | 2023.06.01 |
댓글