BOJ 1305 광고

광고는 전광판의 크기만큼 보여지고, 길이가 N인 광고를 무한히 붙여서 한 칸씩 움직이며 나타나게 한다.
전광판의 크기와 현재 보여지는 문자열(길이가 N인 광고를 무한히 붙였을 때, 전광판의 크기만큼 보여지는 부분)이 주어질 때, 가능한 광고의 길이 중 가장 짧은 길이N을 구하는 문제이다.

어떻게 풀어야할까? 예전에 백준님의 풀이를 보고 풀었는데 기억이 안난다. 힌트로는 알고리즘 분류는 kmp알고리즘으로 되어있다.

kmp로 생각해보자. 문제에서 주어진 예제 aabaaa와 aaaaa로 생각을 해보면, 각 문자열에 해당하는 pi값을 구하고 그 값을 문자열의 길이에서 빼준 것이 답이되는 것 같아보인다.
 일단 aabaaa에서 보면 pi=2, prefix suffix가 같은 최대의 부분 문자열이 aa이다. 길이가 N인 광고가 계속 이어져 있는 것을 생각하면 prefix aa는 앞 광고의 suffix aa로 볼 수도 있을 것이다. 즉 baaa가 원래 광고이고, baaa앞의 aa는 baaa의 suffix aa가 채우고 있는 것으로 볼 수 있는 것이다.

최대를 찾는다면 당연히 aabaaa이렇게 전체가 되겠지만 최소를 찾는다면 aa를 뺀 길이가 된다.