P1305

[baekjoon-1305] 광고

풀이 과정

문제를 분석하기를, 앞서 풀었던 문자열 검색 문제에서는 찾으려는 문자열 패턴이 주어지고, 그 패턴에 해당하는 문자열을 찾으려는게 과제였다. 하지만 이번 문제에서는 반대로 특정 패턴이 반복되는 문자열에서 패턴을 찾는 것이 과제였다.

시간 효율을 생각해보았을 때, L의 최대 크기가 100만이므로 주어진 문자열을 단 한 번만 for문으로 훑어서 답을 도출해야 한다. 그랬을 때 다음과 같은 생각이 이어졌다.

위와 같은 방식으로 현재 검사하려는 문자열 길이에서 접두사와 접미사가 같은 구간의 길이를 빼주면 반복되는 문자열 패턴 및 그 패턴의 길이를 도출할 수 있다.

이 때, 패턴이 3번 이상 반복되는 경우는?

마찬가지로 위와 같이 같은 방식으로 구할 수 있다.

KMP 알고리즘에서 makePk 함수는 문자열에서 접두사와 접미사가 같을 수 있는 최대의 길이를 배열에 저장한다. 이 함수를 통해 도출되는 값을 이용하면 원하는 답을 찾을 수 있다.