Manacher's algorithm

Manacher's Algorithm

시간복잡도 O(N)

문자열의 길이 N만큼의 숫자 배열 A를 만든다.
이 때 A[i]는 i를 중심으로 한 팰린드롬의 최대길이이다.
-> str[i-a[i] : i + a[i]] 는 팰린드롬 문자열이고 str[i-a[i]-1  :  i + a[i]+1] 은 팰린드롬이 아니다.

알고리즘 진행
1. i 는 0 ~ N-1까지 진행된다.
2. j < i인 모든 j에 대해 max(j + A[j])를 구해준다. 이 때 j가 되는 아이를 p라고 하고 p + A[p]를 r이라고 한다.
3. i와 r의 관계에 대해 A[i]의 초기값이 정해진다.
    i  >   r 인 경우, i 이전의 팰린드롬 중 i를 포함하는 팰린드롬이 없다. A[i]는 0

    i <= r 인 경우,  i는 p를 중심으로 하는 팰린드롬에 포함된다.
    이 때 p를 중심으로 하는 팰린드롬에서 i와 대칭되는 애의 위치는 p*2 - i 이다.  이것을 h라고 하자.
       * (p -( i - p)) p에서 i와 p의 거리차이만큼 뒤로 간 위치
    A[h]  < r - i 이면,  i를 중심으로 하는 팰린드롬이 A[h]만큼은 팰린드롬을 가질 수 있는 크기가 확보되었다는 것이고
    A[i] = A[h]이다. 즉 while 문을 돌면서 A[i]값이 더이상 증가하지 않는다.
    A[h] 가 이미 결정되어있다 - > str[h + A[h] +1] != str[h - A[h] -1]이고
    - > str[i + A[h] + 1] != str[i - A[h] - 1] 이므로 A[i]값은 더이상 증가하지 않는다.

    A[h] == r-i 인 경우에는, 
    h를 중심으로 하는 팰린드롬이 p를 중심으로 하는 팰린드롬의 prefix란 것이고,
    r이 문자열의 끝이면 더 이상 증가할 가능성이 없으므로 A[i] = A[h]이다.
    r이 문자열의 끝이 아니라면 더 증가할 가능성이 있으므로 A[i] >= A[h]
   
    r - i  < A[h] 인 경우는 어떨까
    위의 경우를 이해했다면, 현재 r - i 만큼은 반드시 팰린드롬이 성립한다는 걸 이해할 수 있다.

빨간색 화살표가 현재 i 라고 하고,
현재 p는 파란색 c,  r은 끝에 있는 b의 인덱스일 것이다.
이 때 A[h]의 범위 안에 r-i 의 범위가 존재한다는것과 마찬가지이므로 
r - i 만큼은 A[h] < r-i 일때 str[ i - A[h] : i + A[h]]가 반드시 팰린드롬을 이룬다는 것이 자명한만큼 자명할 것이다.

참고 ) 

https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/

https://algospot.com/wiki/read/Manacher%27s_algorithm