one Book a Day

기존 마나커 탐색에 1. 중심이 #이 아닐때(크기1짜리 펠린드롬) 2. 반지름 갱신시 #을 뺀 반지름의 크기만큼 펠린드롬수 추가 3. 범위 확장 시 확장된 범위가 #범위가 아니면 펠린드롬 추가 import sys input = sys.stdin.readline def manacher(string): n = len(string) a = [0] * n # i번째 문자를 중심으로 하는 가장 긴 팰린드롬 반지름 크기. c = 0 # 중심점(center) 초기화 r = 0 # 시작점에서 가장 먼 반경(펠린드롬 끝나는 인덱스중 가장 큰 값.) answer = 0 for now in range(n): if string[now] != '#': answer +=1 # i번째 문자가 now 아래쪽에 있는 문자를 중심으로 ..

Manacher's 알고리즘 : 펠린드롬 탐색. 문자열에서 i번째 문자를 중심으로 하는 가장 긴 팰린드롬 길이를 반지름 r을 저장해 사용한다. O(N)에 다끝나버린다. ## 동작방식 i는 배열의 길이만큼 진행된다. 짝수 팰린드롬 경우 #으로 패딩을 주어 진행한다.(강제로 홀수만듬) aa -> #a#a# a 배열에는 해당 인덱스를 중심으로 한느 가장 긴 팰린드롬의 길이를 저장한다. 반지름 길이를 저장한느 것이지만 #으로 확장 시켰으므로 전체 길이가 된다. r, c변수 r : 해당 인덱스까지 가장 긴 팰린드롬의 우측 끝 c: 해당 인덱스까지 가장 긴 팰린드롬이 중심 인덱스 팰린드롬이라고 정해져 있는 인덱스에 속해 있는지 검사하며 a[i]값을 초기화한다. #b#a#n#a#n#a# -> a의 경우 이미 ..