[알고리즘] Manacher's 알고리즘 : 원 반경에 따라 펠린드롬 최소길이를 보장

Manacher's 알고리즘 : 펠린드롬 탐색.

• 문자열에서 i번째 문자를 중심으로 하는 가장 긴 팰린드롬 길이를 반지름 r을 저장해 사용한다.
• O(N)에 다끝나버린다.

## 동작방식

1. i는 배열의 길이만큼 진행된다.

2. 짝수 팰린드롬 경우 #으로 패딩을 주어 진행한다.(강제로 홀수만듬)

   aa -> #a#a#

3. a 배열에는 해당 인덱스를 중심으로 한느 가장 긴 팰린드롬의 길이를 저장한다.

   반지름 길이를 저장한느 것이지만 #으로 확장 시켰으므로 전체 길이가 된다.

4. r, c변수

   • r : 해당 인덱스까지 가장 긴 팰린드롬의 우측 끝
   • c: 해당 인덱스까지 가장 긴 팰린드롬이 중심 인덱스

5. 팰린드롬이라고 정해져 있는 인덱스에 속해 있는지 검사하며 a[i]값을 초기화한다.

   • #b#a#n#a#n#a# -> a의 경우 이미 n에 해당하는 인덱스에서 #까지가 팰린드롬에 해당한다는 것을 체크하여 r이 #인덱스에 해당하는 8의 값을 가진다. 따라서 기본 a [a인덱스]의 초기값이 1이 된다. (코드 보고 이해)

6. 양 끝 배열에서 벗어나지 않고 문자가 같다면 a[i]의 값을 늘려준다.

   
   

def manacher(string):
    a = [0] * len(string)  # i번째 문자를 중심으로 하는 가장 긴 팰린드롬 반지름 크기.
    c = 0  # 중심점(center) 초기화
    r = 0  # 시작점에서 가장 먼 반경(펠린드롬 끝나는 인덱스중 가장 큰 값.)

    for i in range(0, len(string)):
        # i번째 문자가 i 아래쪽에 있는 문자를 중심으로 하는 팰린드롬 범위 밖의 문자라는 뜻.
        # 때문에 i 이전에 얻은 정보를 재활용하지 못하고 i를 기준으로 초기화시켜 재계산함.
        if r < i:
            a[i] = 0
        # i번째 문자가 i미만의 문자를 중심으로 하는 팰린드롬에 속한다면?
        # 1. i를 중심으로 하는 가장 긴 팰린드롬이 기존 최장 팰린드롬인 c를 중심으로 하는 가장 긴 팰린드롬에 완전히 속하는 경우 -> i의 c점에 대한 대칭점 i'을 기준으로 하는 펠린드롬은 i를 기준으로 하는 팰린드롬과 완전한 대칭. a[i]=a[i']인데 p[i']은 이전에 구해놓았기 때문에 연산 안해도됨.
        # 2. i를 중심으로 하는 가장 긴 팰린드롬이 c를 중심으로 한느 가장 긴 팰린드롬에 일부만 포함된느 경우 -> 초기 반지름 a[i] = ((c+a[c])-i)가 보장이됨(가장 긴 펠린드롬의 오른쪽 한계로부터 i만큼 왼쪽으로 줄인 반지름에서 (c+a[c])-i+1부터 비교 시작)
        # 3. i를 중심으로 한느 가장 긴 팰린드롬이 c < i인 c를 중심으로 하는 가장 긴 팰린드롬과 겹치는 경우. (c의 날개와 i의 날개가 동일지점인 경우)
        # 역시 case 2처럼 a[i] = ((c+a[c])-i)만큼의 반지름이 보장이 됨. 그 이후로 부터 비교하면 됨. i'은 (2*c)-i이므로 i'의 날개와 r-i값중 더 작은 곳을 보장받고 움직이면 됨.
        else:
            a[i] = min(a[(2*c) - i], r - i)

        # i번째 인덱스 기준 가장 긴 펠린드롬 반지름을 펼쳤을 시 0~len(s)의 범위 안에 존재해야하며
        # i기준 a[i](반지름)만큼 펼친 그 양옆문자도 같으면?(-1.+1인덱스가 같으면)
        # a[i]+1(반지름 확장)
        while(i-a[i]-1>=0 and i+a[i]+1 < len(string) and string[i-a[i]-1] == string[i+a[i]+1]):
            a[i] = a[i] + 1
        # 시작점에서 가장 먼 반경인 i + a[i]가 기존 최장 반지름 길이 r보다 크므로
        # r초기화, 중심점 c는 현재 최장 펠린드롬의 중심점인 i로 초기화.
        # 결국 r,c는 현 시점에서 가장 먼 팰린드롬의 날개값(가장 멀리갈때 초기화됨.)
        # a[i]가 0이어도 r보다 i가 커지면 갱신됨.
        if (r < i + a[i]):
            r = i + a[i]
            c = i
    return max(a)