공부정리

짧은 길이의 문자열에서 최대 팰린드롬 길이를 구하려면 dp를 사용하면 된다.

하지만 문자열이 길어지면 dp보다 suffix array를 이용하는게 낫다.

suffix array를 이용해 팰린드롬을 구하는 방법은

(문자열)이 주어지면 문자열에 등장하지 않는 문자를 하나 끼워넣고 뒤에 문자열을 뒤집어서 붙인다.

(문자열)#(열자문)을 만들고 suffix array를 만들고 중간의 # 기준으로 좌우의 suffix array의 LCP(Longest Common Prefix)의 길이를 조사한다.

부분문자열은 suffix의 prefix이며 팰린드롬이라면 기존 문자열과 뒤집은 문자열에 동일하게 등장하기 때문이다.