문자열에서 가장 긴 회문 부분 문자열을 찾기 위해 Manacher 알고리즘을 사용할 수 있습니다. 각 문자를 선택하여 왼쪽 및 오른쪽 포인터를 사용하여 회문이 있는지 찾습니다. 정보를 저장하는 또 다른 배열이 있습니다. 이 정보에서 회문의 길이를 쉽게 찾을 수 있습니다. 각 문자에 대해 배열에 정보가 저장됩니다. 전체 문자열을 탐색한 후 생성된 배열에서 가장 긴 회문 부분 수열을 찾을 수 있습니다.
이 알고리즘의 시간 복잡도는 O(n)입니다.
입력 및 출력
Input: String: “levelup” Output: Longest palindrome is: level
알고리즘
longestPalindrome(text)
입력 - 가장 긴 회문을 찾는 텍스트
출력 - 텍스트에서 가장 긴 공통 회문
Begin n := text size if n = 0, then return null string n := 2n+1 define array longPal of size n longPal[0] := 0 and longPal[1] := 1 centerIndex := 1 rightIndex := 2 right := 0 maxPalLength := 0 maxCenterIndex := 0 start := -1 and end := -1, diff := -1 for right := 2 to n-1, do left := 2*centerIndex – right longPal[right] := 0 diff := rightIndex – right if diff > 0, then longPal[right] := minimum(longPal[left], diff) while (right + longPal[right]) < n AND (right - longPal[right]) > 0 AND (right + longPal[right]+1)mod 2 = 0 OR text[(right + longPal[right] + 1)/2] = text[(right - longPal[right]-1)/2], do increase longPal[right] by 1 done if longPal[right] > maxPalLength, then maxPalLength := longPal[right] maxCenterIndex := right if (right + longPal[right]) > rightIndex, then centerIndex := right rightIndex := right + longPal[right] done start := (maxCenterIndex – maxPalLength)/2 end := start + maxPalLength – 1 palindrome = substring of text[start..end] return palindrome End
예시
#include<iostream> using namespace std; int min(int a, int b) { return (a<b)?a:b; } string longestPalindrome(string mainString) { int n = mainString.size(); if(n == 0) return ""; n = 2*n + 1; //count the next position int longPal[n]; //array to store longest palindrome length longPal[0] = 0; longPal[1] = 1; int centerIndex = 1; int rightIndex = 2; int right = 0, left; int maxPalLength = 0, maxCenterIndex = 0; int start = -1, end = -1, diff = -1; for (right = 2; right < n; right++) { left = 2*centerIndex-right; //calculate left position using center and right longPal[right] = 0; diff = rightIndex - right; if(diff > 0) longPal[right] = min(longPal[left], diff); while ( ((right + longPal[right]) < n && (right - longPal[right]) > 0) && ( ((right + longPal[right] + 1) % 2 == 0) || (mainString[(right + longPal[right] + 1)/2] == mainString[(right - longPal[right] - 1)/2] ))) { longPal[right]++; } if(longPal[right] > maxPalLength) { //max palindrome length maxPalLength = longPal[right]; axCenterIndex = right; } if (right + longPal[right] > rightIndex) { centerIndex = right; rightIndex = right + longPal[right]; } } start = (maxCenterIndex - maxPalLength)/2; end = start + maxPalLength - 1; string palindrome; for(int i=start; i<=end; i++) palindrome += mainString[i]; return palindrome; } int main(int argc, char *argv[]) { string mainString, palindrome; cout << "Enter String:"; cin >> mainString; palindrome = longestPalindrome(mainString); cout << "Longest palindrome is: " << palindrome << endl; }
출력
Enter String: levelup Longest palindrome is: level