문제
문제 링크 : https://www.acmicpc.net/problem/1701
해석
이 문제는 주어진 문자열에서 부분 문자열을 찾을 수 있는지에 대한 것을 물어보는 문제이다.
이때 가장 중요한 점은 '시간내에 찾을 수 있는 지'이다.
따라서 KMP 알고리즘을 알고 있다면 접근이 쉽다.
일반적으로 문자열에서 패턴이 포함되어있는지 찾기 위해선
문자열의 길이 만큼 반복해서 찾는 방법을 생각할 수 있다.
하지만 이 방법은 문자열의 길이가 N, 패턴의 길이가 M이라고 가정했을 때 시간복잡도가 O(NM) 만큼 걸리는 것을 확인할 수 있다. 이는 상당히 비효율적이다.
시간복잡도를 줄일 수 있는 방법 중 하나가 KMP 알고리즘이다.
KMP 알고리즘
KMP 알고리즘은 패턴의 접두사와 접미사를 비교하면서 패턴의 정보를 배열에 저장하면서 시작한다.
이렇게 패턴의 맨 앞 부분 부터 한 글자씩 늘려가며 접두사와 접미사가 동일한 경우 최대 길이를 배열에 저장한다.
다음은 문자열: ABCAABCABAA, 패턴: ABCAB 이라 가정하고 문자열에서 패턴이 있는지 찾는 과정이다. 
i=0 부터 3까지 일치하기 때문에 pattern[3]이 1 인 것을 참고해서
패턴의 위치를 4(일치하지 않은 부분) - 1(pattern[3])으로 옮긴다.
이후 또 i를 1씩 증가시키며 패턴 비교하고... 일치하는 부분을 발견 할 수 있다.
이렇게 KMP 알고리즘을 사용하면 전에 일치 했던 것을 참고해서 O(N+M)의 시간복잡도 안에 문자열에서 패턴과 일치하는 부분을 찾을 수 있다.
문제 풀이
문제로 돌아가서...
입력에서는 문자열만 주어지고
주어진 문자열에서 나올 수 있는 부분문자열 중에 2번이상 찾을 수 있는 문자열을 찾고 그 중 길이가 최대인 것의 길이를 출력해야 한다.
이때 아까 패턴을 저장하는 배열을 구한 방식을 사용하면...
배열에 저장되는 숫자가 접두사와 접미사가 일치할 때의 최대길이기 때문에 접두사, 접미사를 부분 문자열이라고 생각하면 자연스럽게 출력 조건에 만족하게된다.
패턴을 구하는 방식이 맨 앞은 고정이고 뒤를 늘려가는 방식이었다. 때문에 그 반대의 상황도 구해야해서 반복문을 사용해 시작 인덱스를 1씩 늘려가며 각각 패턴의 정보가 저장된 배열을 구하면 그 배열들의 저장된 최대 값이 정답이된다.
코드
def getPattern(text: str) -> list[int]:
pattern = [0] * len(text)
prefix_idx = 0 # 접두사
for suffix_idx in range(1, len(text)): # 접미사
while prefix_idx > 0 and text[suffix_idx] != text[prefix_idx]:
prefix_idx = pattern[prefix_idx - 1]
if text[suffix_idx] == text[prefix_idx]:
prefix_idx += 1
pattern[suffix_idx] = prefix_idx
return pattern
def solution():
text = input()
answer = 0
for i in range(len(text)):
answer = max(answer, max(getPattern(text[i:])))
print(answer)
solution()