manacher 응용문제로 이해력 높이기 - 회문인 부분문자열의 개수를 찾는법

1. 문제

 

16163번: #15164번_제보 (acmicpc.net)

16163번: #15164번_제보

 

2. 풀이

 

연속인 부분문자열에서 회문의 개수를 구하는 문제

 

manacher 알고리즘을 수행하면서, 나타나는 회문의 개수를 세면 될 것이다...

 

그런데 회문의 개수를 어떻게 세야할까

 

예를 들어 ABCBA에 대해서..

 

manacher 알고리즘을 수행하기 위해 #을 붙여가지고

 

#A#B#C#B#A#으로 바꾸고 나서.. 각 index에 대해서 양쪽으로 확대해나가 회문인지 찾아나갈텐데

 

A배열은 각 위치에서 가장 긴 회문의 반지름 길이를 나타내는 것으로, 

 

가장 긴 회문의 반지름 길이를 알고 있다면, 이는 그보다 작은 회문도 포함하고 있는거니까,

 

이 값을 이용한다면 해당 지점에서 회문의 개수를 찾을 수 있을 것이다.

 

계산해본다면...

 

[0, 1, 0, 1, 0, 5, 0, 1, 0, 1, 0]

 

각각이 나타내는 의미를 생각해본다면?

 

C위치에서 5인데.. 

 

 

위 그림과 같은 의미잖아

 

그러니까 ABCBA, BCB, C로 3개가 있는데.. 이는 A배열의 값인 5를 2로 나눈 몫에 1을 더한 값과 같다

 

마찬가지로 A,B,B,A 각각 위치는 1인데...

 

실제로 거기서 회문은 1개잖아.. 역시 1을 2로 나눈 몫에 1을 더한 값과 같다..

 

그러면 다른 예시로 ABCCBA를 생각해본다면..

 

#A#B#C#C#B#A#으로 바뀌고..

 

[0, 1, 0, 1, 0, 1, 6, 1, 0, 1, 0, 1, 0]

 

인데.. 중간에 #에서 6의 의미는..?

 

 

그러면 중간 부분에서 회문을 찾아보면..

 

ABCCBA, BCCB, CC로 3개이다.

 

그래서.. 6을 2로 나눈 몫의 개수와 같다

 

manacher 알고리즘을 이용해 A배열을 채우고.. A배열의 값이 짝수라면 그 지점에서 회문인 부분문자열의 개수는 2로 나눈 몫과 같다.

 

A배열의 값이 홀수라면, 그 지점에서 회문인 부분문자열의 개수는 2로 나눈 몫에 1을 더한 값과 같다.

 

from sys import stdin

s = stdin.readline().rstrip()

s = "#"+"#".join(s)+"#"

n = len(s)

A = [0]*n

r = -1
p = -1

answer = 0

for i in range(n):
    
    if r < i:
        
        A[i] = 0
    
    else:
        
        ii = 2*p-i
        A[i] = min(r-i,A[ii])
    
    while i-A[i]-1 >= 0 and i+A[i]+1 < n and s[i-A[i]-1] == s[i+A[i]+1]:
        
        A[i] += 1
    
    if A[i] % 2 == 0:
        
        answer += (A[i]//2)
    
    else:
        
        answer += (A[i]//2+1)
    
    if i+A[i] > r:
        
        r = i+A[i]
        p = i


print(answer)