Manacher's Algorithm

참조 1 : http://blog.naver.com/jyuno426/220794422838

참조 2 : https://algospot.com/wiki/read/Manacher's_algorithm

회문에 관한 알고리즘이라고 한다. 각 문자를 중심으로 하는 팰린드롬을 알아내는 알고리즘이라고

함. 각 문자를 중심으로하기때문에 짝수 길이의 팰린드롬은 찾을수 없다고 한다. 찾으려면

더미 문자를 끼워넣어서 a#b#c#d#d#c#b#a 꼴로 만들면 된다고 한다.

ex) aaa의 중심은 중간의 a이고, 팰린드롬은 a와 aaa두개가 있다.

aabaa의 중심은 b이고 팰린드롬은 b, aba, aabaa가 있다고 한다. 알고리즘 부분은 알고스팟에서

그대로 가져왔다.

알고리즘은 다음과 같다:

1. i는 0부터 n−1(n=|S|)까지 진행된다
2. j<i인 모든 j에 대해 R=max(j+A[j])이라하고, 또한 그러한 j를 p라 하자. 즉, R=p+A[p]
3. i≤R인지 여부에 따라 A[i]의 초기값이 정해진다
   • i>R이라면, A[i]의 초기값은 0이다.
   • i≤R이라면, i는 p를 중심으로 한 팔린드롬에 속한다는 이야기이다. 이때 p를 중심으로 i의 대칭점 i′을 구한다. (즉, i′=2∗p−i) A[i]의 초기값은 min(R−i,A[i′])으로 둔다.
4. A[i]의 초기값에서부터, S[i−A[i]]과 S[i+A[i]]가 같을 때까지 A[i]를 증가시키고, 그 다음 i로 넘어간다.

코드. 참조 1링크에서 그대로 가져온 코드. (문제시 지우겠습니다. 댓글달아주세요.)

http://koistudy.net/?mid=prob_page&NO=1303 를 푸는 코드라함. 

#include <cstdio>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
    
const int Lmax = 2000010;
char s[Lmax];
int r[Lmax];

void init()
{
	scanf("%s",s);
	int n = strlen(s),i;
	for(i=2*n-2;i>=0;i--)
	{
		if(i%2==0) s[i] = s[i/2];
		else s[i] = '#';
	}
}

void solve()
{
	long long ans = 0;
	int i,j,p,rmax;
	int n = strlen(s);
	p = rmax = -1;
	printf("n = %d\n",n);
	for(i=0;i<n;i++)
	{
		if(i<=rmax) 
			r[i] = min(rmax-i,r[2*p-i]);
		for(j=r[i]+1;i-j>=0 && i+j<n;j++)
		{
			if(s[i-j]==s[i+j]) r[i]++;
			else break;
		}
		if(rmax<i+r[i])
		{
			p = i;
			rmax = p+r[p];
		}
	}

	for(i=0;i<n;i++)
	{
		if(i%2==0) ans += r[i]/2+1;
		else ans += (r[i]+1)/2;
	}
	printf("%lld\n",ans);
}

int main()
{
	init();
	solve();
    return 0;
}

파이썬 버전.

# -*- encoding: cp949 -*-
s = list(raw_input())
n = len(s)
s += [0 for i in xrange(200000)]
r = [0 for i in xrange(200000)]

for i in xrange(2*n-2,-1,-1):
    if i%2==0:
        s[i] = s[i/2]
    else:
        s[i] = '#'

ans = 0
p = rmax = -1
n = 2*n-1
for i in xrange(n):
    if i <= rmax:
        r[i] = min(rmax - i, r[2*p - i])
    j = r[i]+1
    while i-j>=0 and i+j<n:
        if s[i-j]==s[i+j]:
            r[i] += 1
        else:
            break
        j += 1
    if rmax < i+r[i]:
        p = i
        rmax = p+r[p]

#print s[:n]
for i in xrange(n):
    if i%2==0:
        ans += r[i]/2 + 1
    else:
        ans += (r[i]+1)/2
#print r[:n+1]
print ans