palindrome1 Manacher's Algorithm Palindrome 문자열이 있을 때 뒤집어도 같은 문자열이라면 이 문자열을 회문(palindrome)이라고 부른다. 예를 들어, "mom", "tattarrattat", "IOI" 등이 있다. 문자열이 palindrome인지 확인하는 방법은 최소 한 번은 스캔해야 하기 때문에 $O(n)$의 시간 복잡도를 가진다. 부분 문자열의 palindrome 그러면 어떤 문자열이 있을 때 palindrome을 만족하는 부분 문자열도 있을 것이다. 한 글자만 놓고 보면 길이가 1인 palindrome을 만족할 테니, 의미 있게 임의의 위치를 중심으로 만들 수 있는 가장 긴 palindrome을 생각해보자. 처음 생각나는 방법은 무식하게 전부 해보는 방법이다. 길이가 1인 palindrome이 있는지 확인하고, 있다면.. 2019. 10. 17. 이전 1 다음
