최장 회문 부분문자열 계산기
글 안에서 앞뒤로 읽어 같은 가장 긴 조각을 찾아 위치까지 표시합니다. 짝수 길이 회문을 빼먹지 않는 이유와 매내처 알고리즘이 왜 빠른지도 함께 보여 줍니다.
400자까지 봅니다.
가장 긴 회문 조각
다시합창합시다
7글자 · 같은 길이 1개 · 회문 조각 모두 3개
다시합창합시다
0번째 자리부터 7글자입니다 (걸러 낸 글자열 기준)
사용 방법
- 1글을 넣습니다.
- 2공백·대소문자·문장부호를 셀지 정합니다.
- 3가장 긴 회문 조각과 그 자리를 확인합니다.
- 4같은 길이의 조각이 여럿이면 모두 나옵니다.
자주 묻는 질문
가능한 모든 가운데에서 좌우로 한 칸씩 넓혀 보면 됩니다. 회문은 가운데를 기준으로 좌우가 같기 때문입니다. 다만 가운데가 두 종류라, 홀수 길이는 글자 하나가 가운데(aba)이고 짝수 길이는 두 글자 사이가 가운데(abba)여서 넓히기를 2n−1번 해야 합니다.
부분문자열은 붙어 있어야 하고 부분수열은 띄엄띄엄 골라도 됩니다. character에서 붙어 있는 회문은 ara(3글자)뿐이지만, h를 건너뛰어도 된다면 carac(5글자)이 됩니다. 같은 글에서 답이 갈리므로 어느 쪽을 묻는지 먼저 정해야 합니다. 이 계산기는 붙어 있는 쪽을 찾습니다.
글자 사이사이에 구분자를 끼워 모든 회문을 홀수 길이로 만든 뒤, 이미 찾은 회문 안쪽은 좌우가 대칭이라는 성질로 계산을 재활용하기 때문입니다. 그래서 각 자리의 반지름을 한 번에 구해 전체가 O(n)이 됩니다. 가운데에서 넓히는 방법은 O(n²)입니다.
있습니다. babad에서 bab과 aba가 둘 다 3글자인 것이 그 예입니다. 길이는 하나로 정해지지만 그 길이를 갖는 조각은 여럿일 수 있어, 이 계산기는 모두 찾아 자리와 함께 보여 줍니다.
공백과 문장부호를 무시하면 됩니다. «다시 합창 합시다»는 공백을 무시하면 일곱 글자가 모두 회문입니다. 다만 그때 찾은 자리는 걸러 낸 글자열 기준이라 원문의 자리와 다릅니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 찾는 것은 «붙어 있는» 조각(부분문자열)입니다. 띄엄띄엄 고르는 최장 회문 부분수열은 다른 문제이며 값도 다릅니다.
- 글자는 유니코드 NFC로 정규화한 뒤 코드포인트 단위로 셉니다. 이모지처럼 여러 코드가 모인 문자는 나뉘어 셉니다.
- «회문 조각의 개수»는 길이 2 이상인 것만 세며, 겹치는 것도 따로 셉니다. aaa 안에는 aa 두 개와 aaa 하나가 있어 3개입니다.
- 옵션으로 걸러 낸 뒤의 글자열에서 찾으므로, 공백·문장부호를 무시하면 표시되는 자리가 원문의 자리와 어긋납니다.
- 400자까지 봅니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.