Algorithms for Searching Maximum-Length Abelian Duplications in Strings
Hyunbin Kim, Da-Jung Cho · 정보과학회 컴퓨팅의 실제 논문지 · 2025
주어진 길이 N의 문자열 X의 두 부분 문자열이 순열 관계일 때, 두 문자열은 서로에 대한 아벨 복제(Abelian duplication)이다. 본 논문에서는 문자열 X의 가장 긴 아벨 복제를 탐색하는 세 가지 알고리즘을 제안한다. 문자열 X가 사용하는 알파벳의 개수를 K라고 할 때, 누적 합(prefix-sum) 기법을 사용하는 O(KN²) 알고리즘과, 누적 합과 해시 함수를 이용하는 O(KN²) 알고리즘, 그리고 문자열 위 임의의 지점부터 양쪽으로 길이를 확장하며 탐색하는 Bi-directional scanning 기반의 지점부터 양쪽으로 길이를 확장하며 탐색하는 Bi-directional scanning 기반의 O(KN²) 알고리즘을 제안 한다.