문자열에서의 최대 길이 아벨 복제 탐색 알고리즘 = Algorithms for Searching Maximum-Length Abelian Duplications in Strings

국문 초록 (Abstract)

주어진 길이 N의 문자열 X의 두 부분 문자열이 순열 관계일 때, 두 문자열은 서로에 대한 아벨 복제(Abelian duplication)이다. 본 논문에서는 문자열 X의 가장 긴 아벨 복제를 탐색하는 세 가지 알고리즘을 제안한다. 문자열 X가 사용하는 알파벳의 개수를 K라고 할 때, 누적 합(prefix-sum)기법을 사용하는 O(KN^2)알고리즘과, 누적 합과 해시 함수를 이용하는 O(N^2)의 알고리즘, 그리고 문자열 위 임의의 지점부터 양쪽으로 길이를 확장하며 탐색하는 Bi-directional scanning 기반의 O(N^2) 알고리즘을 제안한다.

다국어 초록 (Multilingual Abstract)

Given a string X of length N, two substrings u and v are called Abelian duplicates if they are permutations of each other. We address the problem of finding the longest Abelian duplication within X. To solve this, we propose three algorithms. Let K represent the size of the alphabet used in X. The first algorithm runs in O(KN^2) time and employs a prefix-sum technique. The second algorithm, which combines prefix-sum with hashing, is an O(N^2) algorithm. The third algorithm, based on a bidirectional scanning approach that expands the search from any point in the string in both directions, is also an O(N^2) algorithm.