매내처 없이 해싱을 이용하여 푸는 방법

매내처는 어떤 문자열 $S$에 대해 모든 위치를 중심으로 하는 가장 긴 팰린드롬 부분 문자열의 길이를 $O(|S|)$에 구할 수 있습니다. 하지만 매내처는 이해하기 까다롭고 생각하고 하는 일이 명확하다보니 이 알고리즘이 대회에 나오는 빈도가 낮습니다. 따라서 충돌만 피할 수 있으면 어떤 부분 문자열 $S'$이 존재하는지 빠르게 파악하는 해싱을 이용하여 가장 긴 팰린드롬 부분 문자열이 있는지, 그리고 그 길이가 최대 몇인지 알아보겠습니다. 먼저, 여기서 말하는 문자열에서 해싱은 롤링 해시을 이용한 라빈-카프를 의미합니다. 여기서는 매내처를 대체하는 방법에 대해서만 설명하겠습니다. 그리고 이 문서는 모두 1-based index로 작성되었습니다. 문자열 $S$가 있습니다. 그리고 $S$를 뒤집은 문자열 $R..
알고리즘 정리 2026. 2. 5. 16:41
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2026/02   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
글 보관함
250x250