백준 1305 광고

https://www.acmicpc.net/problem/1305

전광판 길이 L이 주어졌을 때 그곳에 광고 문자열이 한칸씩 옆으로 이동하면서 보여준다고하자. 이 때 광고는 길이 N인 문자열이 무한히 붙여져서 광고된다고 했을 때 어느 순간 전광판을 봤을 때 쓰여 있는 문자가 입력으로 주어졌을 때 가능한 광고의 최소 길이를 구하는 문제이다.

마찬가지로 fail함수를 활용해서 접두사와 접미사가 같은 지점을 활용해주는 문제이다. 생각해보면 AB라는 두 패턴으로 구성된 광고가 주어졌다고 했을 때 ABABA로 B지점이 짤렸다고하자. 그러면 마지막 문자의 접두사와 접미사가 같은 지점을 찾아주면 ABA로 전체 길이에서 해당 길이를 빼주면 AB의 길이가 정상적으로 나타나게 된다. 한칸씩 옆으로 이동하게 되면 달라지는 것이 아닌가 생각할 수 있지만 A, B를 새로운 패턴으로 인식하기만 하면 되기 때문에 똑같은 광고의 길이를 얻게 된다.

예시로 aab라는 광고를 한다고 생각해보자. 길이가 7인 전광판에 광고를 한다고 했을 때 시작은 다음과 같다.

aabaaba

이 때 a를 A패턴 ab를 B패턴이라고 생각하면 결국에는 ABABA 형태로 볼 수 있다. 옆으로 한칸 이동했을 때는 다음과 같다.

abaabaa

이 때는 a를 A패턴 ba를 B패턴이라고 생각하면 결국에는 ABABA 형태가 나타나게 된다. 따라서 주어진 문자열 S에서 마지막 문자의 pi값을 찾아주고 전체 광고판 길이 L에서 빼주게되면 광고의 가장 짧은 길이를 구할 수 있다.

• 전체 코드

func makepi(str: [Character]) -> Int {
    var pi = Array(repeating: 0, count: str.count)
    var j = 0
    for i in 1..<str.count {
        while j > 0 && str[i] != str[j] {
            j = pi[j-1]
        }
        if str[i] == str[j] {
            j += 1
            pi[i] = j
        }
    }
    return pi.last!
}

let L = Int(readLine()!)!
let S = readLine()!.map{Character(String($0))}
let last = makepi(str: S)
print(L-last)