가장 긴 팔린드로믹 하위 문자열

컴퓨터 과학에서 가장 긴 팔린드로믹 변위 문자열이나 가장 긴 대칭 요인 문제는 역시 팔라인드인 주어진 문자열의 최대 길이 연속 변위 문자열을 찾는 문제다. 예를 들어, "바나나"의 가장 긴 팔린드로믹 하위 문자열은 "아나나"이다. 가장 긴 팔린드롬 하위 문자열은 고유하다고 보장되지 않는다. 예를 들어, "아브라카다브라" 문자열에는 길이가 3보다 큰 팔린드롬 하위 문자열은 없지만, 길이가 3인 두 개의 팔린드롬 하위 문자열, 즉 "aca"와 "ada"가 있다. 일부 애플리케이션에서는 하나의 하위 문자열만 반환하거나 최대 길이의 팔린드롬 하위 문자열을 반환하지 않고 모든 최대 팔린드롬 하위 문자열(즉, 더 큰 팔린드롬 하위 문자열로 확장할 수 없는 모든 하위 문자열)을 반환해야 할 수 있다.

Manacher(1975)는 주어진 문자열의 시작에 나타나는 모든 팔레드롬을 나열하는 선형 시간 알고리즘을 발명했다. 그러나, 예를 들어, 아포토리코, 브레슬라우어 & 갈릴(1995)에 의해 관측된 바와 같이, 입력 문자열 내의 어느 곳이나, 다시 선형 시간 내에, 모든 최대 팔린드로믹 서브스트링을 찾는 데 동일한 알고리즘을 사용할 수 있다. 따라서, 그것은 가장 긴 팔린드로믹 변위 문제에 선형적인 시간 해결책을 제공한다. 대체 선형 시간 솔루션은 쥬링(1994년)과 구스필드(1997년)가 제공했는데, 구스필드는 접미사를 이용한 솔루션을 설명했다. 효율적인 병렬 알고리즘도 이 문제로 알려져 있다.^[1]

가장 긴 팔린드롬 하위 문자열 문제는 가장 긴 팔린드롬 하위열을 찾는 다른 문제와 혼동해서는 안 된다.

슬로우 알고리즘

이 알고리즘은 Manacher의 알고리즘보다 느리지만 Manacher의 알고리즘을 이해하는 데 좋은 디딤돌이 된다. 그것은 각 문자를 회심의 중심으로 보고 그 중심과 함께 가장 큰 회랑을 결정하기 위해 순환한다.

함수 중앙의 루프는 길이가 홀수인 팔린드로만 작동한다. 입력 문자열을 수정하여 짝수 길이 팔레드로 기능한다. ' ' 문자는 입력 문자열의 모든 문자 사이에 삽입되며, 양쪽 끝에는 삽입된다. 그래서 입력 "book"은 "b o o k "가 된다. "책"의 짝수 길이의 팔라인드롬 "oo"는 홀수 길이의 팔라인드롬 " o "가 된다.

    Longest_Palindrome_SLOW(string S) {         string S' = S with a bogus character (eg. ' ') inserted between each character (including outer boundaries)         array PalindromeRadii = [0,...,0] // The radius of the longest palindrome centered on each place in S'         // note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1                  Center = 0         while Center < length(S') {             // Determine the longest palindrome starting at Center-Radius and going to Center+Radius             Radius = 0             while Center-(Radius+1) >= 0 and Center+(Radius+1) < length(S') and S'[Center-(Radius+1)] = S'[Center+(Radius+1)] {                 Radius = Radius+1             } // 어레이 PalindromeRadi[Center] = Radius Center = Center+1 } 가장 긴_Palindrome_in_S' = 2*max(PalindromeRadii)+1 가장 긴_Palindrome_in_S'-1) = (long_palindrome_S-1)/2 리턴 론게스트_팔린드롬_in_S }

이 알고리즘의 런타임은 $O(n^{2})$ ( $O(n^{2})$ $O(n^{2})$ ) $O(n^{2})$ 입니다 $O(n^{2})$ 외부 루프는 $n$ $n$ 회 $n$ 실행되며 내부 루프는 $n/2$ n / $n/2$ $n/2$ 회 $n/2$ 실행될 수 있다.

마나허 알고리즘

아래는 Manacher 알고리즘의 유사점이다. 이 알고리즘은 다른 팔라인드롬 안에서 팔라인드롬이 발생할 때 악용되기 때문에 이전 알고리즘보다 속도가 빠르다.

예를 들어 입력 문자열 "abacaba"를 고려하십시오. "c"에 도달할 때까지, Manacher의 알고리즘은 "c" 이전의 글자들을 중심으로 모든 갈림길이의 길이를 확인할 것이다. "c"에서는 "c"를 중심으로 한 가장 큰 팔자 구역을 식별하기 위한 루프를 실행한다. "abacaba"이다. 그런 지식으로 'c' 이후의 모든 것은 'c' 이전의 모든 것을 반사하는 것처럼 보인다. "c" 뒤의 "a"는 "c" 이전의 "a"와 같은 긴 구역을 가지고 있다. 마찬가지로, "c" 뒤에 있는 "b"는 "c" 이전의 "b"를 중심으로 한 가장 긴 팔라인드롬의 길이인 가장 긴 팔라인드롬을 가지고 있다. 고려해야 할 몇 가지 특별한 경우가 있지만, 그러한 속임수는 계산 속도를 극적으로 향상시킨다.

    Longest_Palindrome(string S) {         string S' = S with a bogus character (eg. ' ') inserted between each character (including outer boundaries)         array PalindromeRadii = [0,...,0] // The radius of the longest palindrome centered on each place in S'         // note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1                  중심 = 0 반지름 = 0, 중심 < 길이(S') { // 루프의 시작 부분에서 반경은 이미 가장 긴 반지름에 대해 하한으로 설정되어 있다.             // In the first iteration, Radius is 0, but it can be higher.                          // Determine the longest palindrome starting at Center-Radius and going to Center+Radius             while Center-(Radius+1) >= 0 and Center+(Radius+1) < length(S') and S'[Center-(Radius+1)] = S'[Center+(Radius+1)] {                 Radius = Radius+1             } // PalindromeRadi[Center] = Radius // 이하에서 가장 긴 회백의 반지름을 저장하면 Center가 증가함             // 사전 계산된 값을 재사용할 수 있는 경우 // 또한 Radius를 0 OldCenter = Center OldRadius = Radius Center = Center+1 // Radius의 기본값은 0으로 설정할 수 있다.              Radius = 0, 센터 <= OldCenter + OldRadius { // 센터>는 오래된 회랑 안에 있고 // 회랑 안의 모든 문자는 그 중심에 반사된 "미러링된" 문자를 가지고 있기 때문에, 우리는// 센터의 미러링 포인트에 대해 미리 계산된 데이터를 사용할 수 있다.                  MirroredCenter = OldCenter - (Center - OldCenter)                 MaxMirroredRadius = OldCenter + OldRadius - Center                 if PalindromeRadii[MirroredCenter] < MaxMirroredRadius {                     PalindromeRadii[Center] = PalindromeRadii[MirroredCenter]                     Center = Center+1                 } else if PalindromeRadii[MirroredCenter] > MaxMirroredRadius {                     PalindromeRadii[Center] = MaxMirroredRadius                     Center = Center+1                 } else { // PalindromeRadii[MirroredCenter] = MaxMirroredRadius                     Radius = MaxMirroredRadius                     break  // exit while loop early                 }} {} {가장 긴_팔린드롬_in_S' = 2*max(PalindromeRadii)+1 가장 긴_팔린드롬_in_S = (가장 긴_palindrome_in_S'-1)/2 반환 가장 긴_팔린드롬_in_S}

특수 케이스

마나허의 알고리즘은 다른 흑백 내부에 흑백(Palindrome)이 존재할 때 미리 계산된 데이터를 재사용하기 때문에 더 빠르다. 이것의 경우는 3가지다. 이러한 문구는 유사 부드의 "if / other if / other" 문장으로 표현된다.

첫 번째 경우는 갈림길이 MirroredCenter "오래된" 구각 안에 완전히 놓여 있다. 이런 상황에서 에 있는 회향은 Center 의 길이와 같을 것이다. MirroredCenter. 예를 들어, "구" 팔자판이 "abcbpbcba"라면, "p" 다음에 "c"를 중심으로 한 팔자형의 길이가 "p" 이전의 "c"를 중심으로 한 팔자형의 길이와 같아야 함을 알 수 있다.

두 번째 경우는 갈림길이 MirroredCenter '오래된' 구각 바깥에 펼쳐져 있어 즉, "왼쪽"으로 확장된다(또는 "구" 구문 안쪽에 있는 어떤 문자보다 낮은 인덱스를 가진 문자를 포함). 왜냐하면 "Old" Palindrome이 중심이 되는 가장 큰 Palindrome이기 때문이다. OldCenter, 우리는 그것의 전과 후의 등장인물이 다르다는 것을 안다. 그래서, 팔목의 끝부분은 Center 다음 등장인물은 다음 등장인물이 다음 등장인물과 다음 등장인물이 다음 등장인물의 종이가 될 것이기 때문에 "오래된" 종묘의 경계선까지 정확히 달릴 것이다. MirroredCenter. 예를 들어, 끈이 "ababc"라면, "Old" 팔린드롬은 "bab"과 함께 "bab"이 될 수 있다. Center 제2의 "b"가 되는 것과 MirroredCenter 첫 번째 "b"가 되는 것. 그 후부터. MirroredCenter "aba"이며 "Old" 구각의 경계를 넘어 확장되며, 두 번째 구각의 가장 긴 구각은 "Old" 구각의 경계까지 확장될 수 있다는 것을 우리는 알고 있다. 우리는 이것을 알고 있다. 왜냐하면 만약 "구" 팔라인드롬 뒤의 캐릭터가 "c"가 아니라 "a"가 되었더라면, "구" 팔라인드롬은 더 길었을 것이기 때문이다.

세 번째와 마지막 경우는 갈림길이 MirroredCenter '오래된' 구각의 경계선까지 정확히 뻗어나간다. 이 경우 '구(舊)' 팔라인드롬 뒤의 캐릭터가 '구(舊) 팔라인드롬'을 만들어낼지 알 수 없다. Center 의 그것보다 더 긴. MirroredCenter하지만 우리는 그 종양이 Center 적어도 에 있는 것만큼 길다. MirroredCenter. 이 경우 Radius 다음 위치에서 흑백 반지름으로 초기화됨 MirroredCenter 수색은 거기서부터 시작된다 예시 문자열은 "abcbpbcbp"이며 여기서 "Old" 팔라인드롬은 "bcbpbcb"이고 Center 두 번째 "C"에 있어 그 MirroredCenter 첫 번째 "c"이고 가장 긴 "bcb" 구역을 가지고 있다. 가장 긴 팔목회지(Galindrome)가 있다. Center 두 번째 "c"는 최소한 그렇게 길어야 하고, 이 경우에는 더 길어야 한다.

런타임

알고리즘은 선형 시간으로 실행된다. 이는 각 루프의 반복 실행 횟수에 한계를 두는 것으로 볼 수 있다. 외부 루프 및 두 번째 내부 루프 증분 Center 반복할 $1$ $1$ 마다 1 $[\displaystyle$ 1}씩 $.$ 이후 Center 문자열의 길이에 의해 제한되며, 이러한 $n$ 는 n{\ $displaystyle n}$ 번 $n$ 실행된다는 것을 알고 있다. 첫 번째 내부 루프 증분 Radius 모든 반복과 두 번째 내부 루프에 대해 $1$ $1$ $[\displaystyle 1}$ 씩 정지할 때 감소 Radius 반복할 때마다 $1$ 최대 $[\displaystyle 1}$ 씩. 두 번째 내부 루프는 최대 $n$ $n$ 번 $n$ 실행될 수 있고 값은 Radius $n/2,$ / 2 , $displaystyle$ n $/2,}$ 을(를) $초과$ 할 수 없음. 첫 번째 내부 루프는 최대 $n+n/2$ + $n+n/2$ / $n+n/2$ ${\$ displaystyle $n+n/2}$ 번 $n+n/2$ 실행될 수 있음. 전체 런타임은 $O\left(n+n+n/2\right)=O(n).$ + n $O\left(n+n+n/2\right)=O(n).$ + $O\left(n+n+n/2\right)=O(n).$ + $O\left(n+n+n/2\right)=O(n).$ / 2 $O\left(n+n+n/2\right)=O(n).$ ) $O\left(n+n+n/2\right)=O(n).$ = $O\left(n+n+n/2\right)=O(n).$ ) $O\left(n+n+n/2\right)=O(n).$ . ${\displaystyle O\left(n+n+n/2\right)=O(n$ )이다 $.$ $}$

메모들

^ 크로쉐모어 & 라이터(1991), 아포토리코, 브레슬라우어 & 갈릴(1995)이다.

참조

Apostolico, Alberto; Breslauer, Dany; Galil, Zvi (1995), "Parallel detection of all palindromes in a string", Theoretical Computer Science, 141 (1–2): 163–173, doi:10.1016/0304-3975(94)00083-U.
Crochemore, Maxime; Rytter, Wojciech (1991), "Usefulness of the Karp–Miller–Rosenberg algorithm in parallel computations on strings and arrays", Theoretical Computer Science, 88 (1): 59–82, doi:10.1016/0304-3975(91)90073-B, MR 1130372.
Crochemore, Maxime; Rytter, Wojciech (2003), "8.1 Searching for symmetric words", Jewels of Stringology: Text Algorithms, World Scientific, pp. 111–114, ISBN 978-981-02-4897-0.
Gusfield, Dan (1997), "9.2 Finding all maximal palindromes in linear time", Algorithms on Strings, Trees, and Sequences, Cambridge: Cambridge University Press, pp. 197–199, doi:10.1017/CBO9780511574931, ISBN 0-521-58519-8, MR 1460730.
Jeuring, Johan (1994), "The derivation of on-line algorithms, with an application to finding palindromes", Algorithmica, 11 (2): 146–184, doi:10.1007/BF01182773, hdl:1874/20926, MR 1272521, S2CID 7032332.
Manacher, Glenn (1975), "A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string", Journal of the ACM, 22 (3): 346–351, doi:10.1145/321892.321896, S2CID 10615419.

외부 링크

Longest Palindromic Substring Part II., 2011-11-20, archived from the original on 2018-12-08. 선형 시간에서 가장 긴 팔린드로믹 하위 문자열을 찾기 위한 Manacher의 알고리즘에 대한 설명.
Akalin, Fred (2007-11-28), Finding the longest palindromic substring in linear time, retrieved 2016-10-01. Manacher의 선형 시간 알고리즘의 설명 및 Python 구현.
Jeuring, Johan (2007–2010), Palindromes, retrieved 2011-11-22. Jeuring의 선형 시간 알고리즘의 Haskell 구현.
Palindromes. Manacher의 선형 시간 알고리즘의 자바 구현.

이 글에는 Creative Commons Attribution(CC-BY-3.0) 라이센스에 따라 PEGWiki의 Loston Palindromic 하위 문자열의 텍스트가 포함되어 있다.

[1] 크로쉐모어 & 라이터(1991), 아포토리코, 브레슬라우어 & 갈릴(1995)이다.

[1]

Search

가장 긴 팔린드로믹 하위 문자열

네임스페이스

더

목차

슬로우 알고리즘

마나허 알고리즘

특수 케이스

런타임

메모들

참조

외부 링크