백준 4354 문자열 제곱
23 Jun 2021https://www.acmicpc.net/problem/4354
문자열 s를 s = a^n의 형태로 표현한다고 했을 때 이는 문자열 a가 n번 반복해서 나오면 s가 된다는 뜻이다. 이때 임의의 문자열이 주어지면 s = a^n을 만족하는 가장 큰 n을 찾는 문제이다.
KMP 알고리즘에 대해 제대로 배워왔다면 쉽게 풀 수 있는 문제이다. 문자열의 실패함수를 이용한다면 해결할 수 있다. 실패함수를 거치면 pi속에는 접두사와 접미사가 같은 부분의 길이가 나타나있다.
만약 특정 패턴 A가 4번 반복된 문자열 S = AAAA 가 주어진다고 생각해보자. AAA라는 패턴으로 접두사와 접미사가 같기 때문에 마지막 문자의 pi값은 AAA가 끝나는 지점을 나타내줄 것이다. 따라서 A 패턴의 길이는 Length of A = string.count - pi[last]가 된다.
이제 A의 길이를 알았으니 전체 문자열 S에서 A의 길이를 뺐을 때 나머지가 A의 길이로 나뉜다면 S-A가 A패턴의 제곱으로 이루어져있다는 것을 알 수 있다. 최종적으로는 S가 A패턴의 제곱으로 이루어져있다면 n = string.count / Length of A로 n을 구할 수 있다.
- 전체 코드
func makepi(str: [Character]) -> [Int] {
var j = 0
var pi = Array(repeating: 0, count: str.count)
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
}
while let line = readLine() {
if line == "." {
break
}
let S = line.map{Character(String($0))}
let pi = makepi(str: S)
let last = pi.last!
let length = S.count - last
if last == 0 || (S.count-length)%length != 0{
print(1)
}
else {
print(S.count / length)
}
}