백준 16163
23 Jun 2021https://www.acmicpc.net/problem/16163
문자열이 주어지면 주어진 문자열 속의 모든 회문의 갯수를 구하는 문제이다. 회문 관련 문제이기 때문에 Manacher 알고리즘을 활용해서 풀 것이다.
기존의 manacher알고리즘을 사용하면 문자열 속 각 자리를 중심으로하는 회문의 길이를 구할 수 있다. 그런데 회문의 길이가 3인 DCBABCD와 같은 회문을 생각해보자. 이때 회문의 양끝을 제거해나간 것도 하나의 회문이 되기 때문에 회문의 길이가 3이면 총 4개의 회문을 얻을 수 있다. 즉 manacher 알고리즘으로 구한 회문의 길이를 통해 회문의 갯수를 파악할 수 있게 된다.
따라서 모든 index의 회문의 길이를 훑으면서 갯수에 더해주면 된다. 유의할 것은 짝수 길이의 회문을 파악하기 위해서 문자열에 #과 같은 문자가 사이사이에 삽입되어있다는 것이다. 이를 고려하여 짝수길이 회문과 홀수길이 회문 case로 나누어서 갯수를 파악해주자.
- 전체 코드
func manacher(str: [Character]) -> [Int] {
let n = str.count
var r = -1, p = -1
var A = Array(repeating: 0, count: n)
for i in 0..<n {
if i <= r {
A[i] = min(A[2*p-i], r-i)
}
while i-A[i]-1 >= 0 && i+A[i]+1 < n && str[i-A[i]-1] == str[i+A[i]+1] {
A[i] += 1
}
if i+A[i] > r {
r = i+A[i]
p = i
}
}
return A
}
let line = readLine()!
var str = [Character]()
str.append("#")
for c in line {
str.append(c)
str.append("#")
}
let pe = manacher(str: str)
var result = 0
for i in 0..<pe.count {
if i%2 == 0 {
result += pe[i]/2
}
else {
result += (pe[i]+1)/2
}
}
print(pe)
print(result)