한 문자열이 주어진다면, 팰린드롬인 가장 긴 문자열을 찾아라. 예르륻ㄹ어, 만약 주어진 문자열이 "forgeeksskeegfor"라면 그 output은 "geeksskeeg"이다.
Method1 (Brute Force)
그 간단한 접근법은 substring이 팰린드롬인지 아닌지를 각각 체크하는 것이다. 우리는 세 개의 loop를돌릴 수 있고, 그 바깥의 두 개의 loops가 모든 부분 문자열을 하나씩 고르는데, 그 corner 문자를 고르고, inner loop는 그 골라진 substring이 팰린드롬인지를 체크한다.
Time Complexity : O(n^3)
Auxiliary complexity : O(1)
Method 2 (Dynamic Programming)
그 시간 복잡도는 부분 문제들의 결과들을 저장하여 줄어들 수 있다. 그 아이디어는 이 포스트와 비슷하다. 우리는 table[n][n]을 bottom up 방식으로 채워진 것을 유지한다. 그 table[i][j]의 값은 true이다, 만약 그 substring이 palindrom이라면, 그렇지 않다면 false이다. table[i][j]를 계산하기 위해, 우리는 처음에 table[i + 1][j - 1]의 값을 체크하고, 만약 그 값이 true이고 str[i]는 str[j]가 같다면, 그러면 우리는 table[i][j]를 true로 만든다. 그렇지 ㅇ낳다면, 그 table[i][j]의 값은 false가 된다.
https://www.geeksforgeeks.org/longest-palindromic-substring-set-2/
우리는 이전 포스트에서 DP 솔루션을 이야기했다. DP 기반 솔루션의 시간 복잡도는 O(n^2)이고, 그것은 O(n^2)의 추가 공간을 요구한다. 우리는 O(n^2) 시간에 O(1) 추가 공간으로 가장 긴 팰린드롬 substring을 찾을 수 있다. 그 아이디어는 모든 짝수 길이와 홀수 길이의 팰린드롬을 생성하고, 이제까지 찾은 가장 긴 팰린드롬을 추적하는 것이다.
홀수 길이의 팰린드롬을 생성하는 단계 : 센터를 고정하고, 더 긴 팰린드롬들에 대해 두 방향으로 팽창해라.
짝수 길이의 팰린드롬을 생성하는 단계 : 두 개의 센터(low and high)를 고정하고, 더 긴 팰린드롬을 위해 두 방향으로 확장해라.
int palinedrom(const string& s) { int maxLength = 1; int len = s.size(); int low, high; for (int i = 1; i < len; ++i) { // Find the longest even length palindrom with center points // as i - 1 and i. low = i - 1; high = i; while (low >= 0 && high < len & s[low] == s[high]) { if (high - low + 1 > maxLength) { maxLength = high - low + 1; } --low; ++high; } // Find the longest odd length palindrom with center point as i low = i - 1; high = i + 1; while (low >= 0 && high < len && s[low] == s[high]) { if (high - low + 1 > maxLength) { maxLength = high - low + 1; } --low; ++high; } } return maxLength; }
시간 복잡도 : O(n^2). n은 입력 문자열의 길이
Auxiliary Space : O(1)
우리는 곧 별개의 포스트로서 좀 더 최적화된 방법을 추가할 것이다.
https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/
우리는 이미 Naive [O(n^3)]와 quadratic [O(n^2)] 접근법을 Set1과 Set2에서 보았다.
이 자료에서, 우리는 가장 긴 팰린드롬 부분 문자열을 선형 시간에 찾는 Manacher's algorithm에 대해 이야기할 것이다.
팰린드롬을 찾는 한 방법(Set 2)는 문자열의 중심에서 시작하여, 양 방향으로 하나씩 문자들을 비교한다. 만약 두 방향에서 대응되는 문자들이 똑같다면, 그러면 그것들은 팰린드롬을 만들 것이다.
"abababa" 문자열을 고려해보자.
문자열의 중심부는 4번째 문자(index 3) b이다. 만약 우리가 그 중심의 왼쪽과 오른쪽에서 문자들이 같다면, 모든 문자들이 부합하고, 그래서 "abababa"는 팰린드롬이다.
여기에서 center position이 실제 string character position일 뿐만 아니라, 두 문자들 사이의 위치가 될 수 있다.
짝수 길이의 "abaaba" 문자열을 고려해라. 이 문자열은 3번째와 4번째 문자열 사이의 위치 주변에서 팰린드롬이다.
길이가 N인 문자열의 가장 긴 팰린드롬 부분문자열을 찾기위해서, 한 방법은 각 가능한 2 * N + 1의 centers를 정하고 (N번째 문자 위치와 N - 1번째, 두 문자 위치 사이의, .~~) 그리고 각 2 * N + 1 센터에서 왼쪽과 오른쪽 방향에서 문자들이 같은지를 보고, LPS를 추적한다. 이 접근법은 O(N^2) 시간이 걸리고, Set2에서 한 것이다.
두 개의 문자열 "abababa"와 "abaaba"를 아래에서 보여진 것처럼 고려하자:
이러한 두 개의 문장려에서, center positions의 왼쪽과 오른쪽 방향은 대ㅣㅇ적이다. 왜? 전체 문자열이 center position에 대해 대칭적이기 때문이다.
만약 우리가 왼쪽에서 오른쪽으로 2 * N + 1에서 가장 긴 팰린드롬 부분 문자열을 계산할 필요가 있다면, 그러면 팰린드롬의 대칭성은 불필요한 연산을 줄이는데 도움이 된다 (즉, 문자 비교). 만약 어떤 위치 P를 중심으로한 어떤 길이 L의 팰린드롬이 있다면, 그러면 우리는 위치 P + 1에서 왼쪽과 오른쪽에 있는 모든 문자들을 비교할 필요가 없다. 우리는 이미 P 이전 위치에서 LPS를 계산했고, 그것들은 P위치 이후의 비교들을 피하는데 도움이 된다.
나중에 이전 위치로부터의 정보의 사용은 Manacher의 알고리즘을 선형으로 만든다. Set2에서, quadratic인, 이전 정보의 재사용이 없었다.
Manacher의 알고리즘은 아마도 이해하기에 복잡하다고 고려되고, 그래서 여기에서 그것을 우리가 할 수 있는 한 상세히 이야기할 것이다. 그것의 어떤 부분들은 적절히 이해하기 위해 여러번 읽을 것이 요구된다.
문자열 "abababa"를 봐보자. 위에서 3번째 그림에서, 15개의 센터 포지션들이 보인다. 우리는 이러한 위치들의 각각에서 가장 긴 팰린드롬 문자열의 길이를 계산할 필요가 있다.
- 위치 0에서, LPS가 없다 (비교할 왼쪽 면에 문자가 없다), 그래서 LPS의 길이는 0일 것이다.
- 위치 1에서, LPS는 a이고, 그래서 LPS의 길이는 1일 것이다.
- 위치 2에서, LPS가 없다 (왼쪽과 오른쪽 문자인 a와 b는 같지 않다), 그래서 LPS의 길이는 0일 것이다.
- 위치 3에서, LPS는 aba이고, 그래서 LPS의 길이는 3일 것이다.
- 위치 4에서, LPS가 없다(왼쪽과 오른쪽 문자인 b와 a는 부합하지 않는다), 그래서 LPS의 길이는 0일 것이다.
- 위치 5에서 LPA는 ababa이고, LPS의 길이는 5일 것이다.
우리는 모든 이러한 팰린드롬의 길이들을 한 배열에 저장한다, L이라고 하자. 그러고나서 문자열 S와 LPS길이 L은 아래처럼 보인다:
유사하게 문자열 "abaaba"의 LPS길이는 다음처럼 보일 것이다:
LPS 배열 L에서:
- 홀수 위치에서 LPS 길이 값 (실제 문자열의 위치)은 홀수이고, 1과 같거나 더 클 것이다.
- 짝수 위치에서 LPS 길이 값 (두 문자들 사이의 위치, 그리고 맨 왼쪽과 오른쪽 위치)은 짝수일 것이고, 0과 같거나 더 클 것이다.
문자열에 대한 위치와 인덱스는 여기에서 두 개의 다른 것들이다. length N의 주어진 문자열 S에 대해, 인덱스들은 0부터 N - 1까지이고 위치들은 0부터 2*N까지 이다 (총 2*N + 1위치).
LPS length value는 두 가지 방식으로 해서될 수 있다, index의 관점에서, 그리고 위치의 관점에서. 위치 l (L[i] = d)에 있는 LPS 값 d은 다음을 말한다:
LPS length value는 두 가지 방식으로 해서될 수 있다, index의 관점에서, 그리고 위치의 관점에서. 위치 l (L[i] = d)에 있는 LPS 값 d은 다음을 말한다:
- 위치 i - d 부터 i + d 까지의 위치의 substring은 길이 d인 팰린드롬이다 (위치의 관점에서)
- index (i -d)/2 부터 (i+d)/2 -1까지의 substring은 길이가 d인 팰린드롬이다 (index의 관점에서
예를들어, 스트링 "abaaba"에서, L[3] = 3은 위치 0 (3-3)부터 6 (3+3)까지의 substring이 길이가 3인 "aba"인 팰린드롬이라는 것을 의미한다.
이제 그 main task는 LPS 배열을 효율적으로 연산하는 것이다. 일단 이 배열이 연산된다면, 그 배열 S의 LPS는 maximum LPS length value를 가진 위치에 집중될 것이다.
우리는 그것을 part 2에서볼 것이다.
우리는 그것을 part 2에서볼 것이다.
Manacher's 알고리즘 Part 1에서, 우리는 몇 가지 기본과 LPS length array를 보았따. 여기에서 우리는 LPS length array를 효율적으로 어떻게 계산하는지를 볼 것이다.
LPS 배열을 효율적으로 계산하기 위해서, 우리는 어떤 위치에 대해 LPS length가 어떤 이전에 이미 계산된 위치의 LPS length value과 관련있는지를 이해할 필요가 있다.
문자열 "abaaba"에 대해, 우리는 다음을 본다:
만약 우리가 position3을 둘러본다면:
우리는 LPS length values를 position 0에서 시작하여 left에서 right로 계산한다. 그래서 우리는 우리가 이미 LPS length values를 위치 1,2 그리고 3에서 값을 아는지를 볼 수 있고, 그러고나서 우리는 위치 4와 5에서 LPS length를 계산할 필요가 없을지도 모른다. 왜냐하면 그것들을 위치 3의 왼쪽 side에서 대응되는 위치에서 LPS length values와 일치하기 때문이다.
만약 우리가 position 6을 둘러본다면:
Case 2는 위치 9, 11, 13 과 14에 적용된다. 그래서:
L[9] = L[5] = 5
L[11] = L[3] =3
L[13] = L[1] = 1
L[14] = L[0] = 0
Case 1과 Case 2에서 무엇이 일어나고 있는가? 이것은 palindromic symmetric property를 활용하는 것이고, 어떤 문자 매칭없이, 그것은 새로운 위치의 LPS 길이를 찾고있다.
더 큰 길이의 팰린드롬이 그것의 center의 left side에 중심을 둔 더 작은 length palindrome을 포함할 때, 그러면 symmetric property를 기반으로, 또 다른 같은 더 작은 팰린드롬이 더 큰 팰린드롬 센터의 오른쪽에 중심에 있을 것이다. 만약 left side smaller palindrome이 더 큰 palindrome의 prefix가 아니라면, 그러면 Case 1이 적용되고, 그것이 prefix이고, 더 큰 팰린드롬이 input string 그 자체의 suffix라면, 그러면 Case 2가 적용된다.
current center의 오른쪽 (i-right palindrome)에 위치한 가장 긴 팰린드롬 i 위치는 current center의 왼쪽에 위치한 가장 긴 palindrom i 위치만큼 길다 (i-left palindrome), 만약 그 i-left palindrome이 current center 주변의 완전히 longest palindrome 안에포함되고, 그 i-left palindrome이 center palindrome의 prefix가 아니라면(Case 1) 또는 (즉, i-left palindrome이 center palindrome의 prefix일 때), 만약 그 center palindrome이 전체 문자열의 suffix라면 (case 2).
Case 1과 Case2에서, i-right palindrome은 대응되는 i-left palindrome 이상으로 확장될 수 없다 (너는 왜 그것이 더 확장할 수 없는지시각화 할 수 있는가?), 그래서 i-right 팰린드롬의 LPS 길이는 정확히 i-left palindrome의 LPS길이와 정확히 같다.
LPS 배열을 효율적으로 계산하기 위해서, 우리는 어떤 위치에 대해 LPS length가 어떤 이전에 이미 계산된 위치의 LPS length value과 관련있는지를 이해할 필요가 있다.
문자열 "abaaba"에 대해, 우리는 다음을 본다:
만약 우리가 position3을 둘러본다면:
- position 2와 position 4에서 LPS length value는 같다.
- position 1과 position 5에서 LPS length value는 같다.
우리는 LPS length values를 position 0에서 시작하여 left에서 right로 계산한다. 그래서 우리는 우리가 이미 LPS length values를 위치 1,2 그리고 3에서 값을 아는지를 볼 수 있고, 그러고나서 우리는 위치 4와 5에서 LPS length를 계산할 필요가 없을지도 모른다. 왜냐하면 그것들을 위치 3의 왼쪽 side에서 대응되는 위치에서 LPS length values와 일치하기 때문이다.
만약 우리가 position 6을 둘러본다면:
- 위치 5와 위치 7에서 LPS length value는 같다
- 위치 4와 위치 8에서 LPS length value는 같다
등등...
만약 우리가 이미 위치 1~6에서 LPS length value를 안다면, 그러고나서 우리는 위치 7~11에서의 LPS length를 계산할 필요가 없을지도 모른다. 왜냐하면 그것들은 위치 6의 왼쪽에서 대응되는 위치에서 LPS 길이 값들이 같기 때문이다.
string "abababa"에 대해, 우리는 다음을 본다:
만약 윌가 이미 위치 1~7에서의 LPS 길이 값을 알고있다면, 그러면 우리는 위치 8~13까지의 위치에서의 LPS길이를 계산할 필요가 없을지도 모른다. 왜냐하면 그것들은 위치 7의 왼쪽에서의 대응되는 위치의 LPS 길이 값과 같기 때문이다.
너는 왜 LPS 길이 값이 문자열 "abaaba"에서 위치 3, 6, 9 주변에서 대칭인지를 알 수 있는가?
그것은 왜냐하면 이 위치 주변에 팰린드롬 부분문자열이 있기 때문이다. 위치 7 주변의 "abababa"도 같은 경우이다.
palindromic center position 주변에서 LPS 길이 값이 항상 대칭이라는 것은 항상 사실인가?
그 답은 NO이다.
문자열 "abababa"에서 위치 3과 11을 보아라. 두 위ㅣ들은 LPS 길이 3을 가진다. 바로 왼쪽과 오른쪽 위치들은 대칭적이다 (값이 0으로), 그러나 다음 것은 아니다. 위치 1과 5는 대치잉 아니다. 유사하게, 위치 9와 13은 대칭이 아니다.
이 지점에서, 우리는 만약 어떤 위치를 중심으로 하는 한 문자열에서 팰린드롬이 있다면, 그러면 그 center position 주변의 LPS 길이 값은 어떤 상황에 따라 대칭이거나 대칭이 아닐지도 모른다. 만약 우리가 그 상황을 확인한다면, left와 right 위치들이 중심 위치와 대칭일 때, 우리는 오른쪽 위치의 LPS 길이를 계산할 필요가 없다. 왜냐하면 그것은 정확히 같기 때문이다, 왼쪽에서의 대응되는 위치의 LPS 값으로서. 그리고 우리가 어떤 위치에서 LPS 길이 계산을 피하려는 이 사실은 Manacher 알고리즘을 선형으로 만든다.
왼쪽과 오른쪽 위치들이 중심위치 주변에서 대칭이 아닐 것이라는 상황에서, 우리는 팰린드롬을 찾기 위해 왼쪽과 오른쪽에서 문자들을 비교하지만, 여기에서 또는 알고리즘은 어떠한 비교를 피하려고 한다. 우리는 모든 이러한 시나리오들을 곧 보게 될 것이다.
더 나아가기 위해 몇 가지 용어들을 소개하자:
string "abababa"에 대해, 우리는 다음을 본다:
만약 윌가 이미 위치 1~7에서의 LPS 길이 값을 알고있다면, 그러면 우리는 위치 8~13까지의 위치에서의 LPS길이를 계산할 필요가 없을지도 모른다. 왜냐하면 그것들은 위치 7의 왼쪽에서의 대응되는 위치의 LPS 길이 값과 같기 때문이다.
너는 왜 LPS 길이 값이 문자열 "abaaba"에서 위치 3, 6, 9 주변에서 대칭인지를 알 수 있는가?
그것은 왜냐하면 이 위치 주변에 팰린드롬 부분문자열이 있기 때문이다. 위치 7 주변의 "abababa"도 같은 경우이다.
palindromic center position 주변에서 LPS 길이 값이 항상 대칭이라는 것은 항상 사실인가?
그 답은 NO이다.
문자열 "abababa"에서 위치 3과 11을 보아라. 두 위ㅣ들은 LPS 길이 3을 가진다. 바로 왼쪽과 오른쪽 위치들은 대칭적이다 (값이 0으로), 그러나 다음 것은 아니다. 위치 1과 5는 대치잉 아니다. 유사하게, 위치 9와 13은 대칭이 아니다.
이 지점에서, 우리는 만약 어떤 위치를 중심으로 하는 한 문자열에서 팰린드롬이 있다면, 그러면 그 center position 주변의 LPS 길이 값은 어떤 상황에 따라 대칭이거나 대칭이 아닐지도 모른다. 만약 우리가 그 상황을 확인한다면, left와 right 위치들이 중심 위치와 대칭일 때, 우리는 오른쪽 위치의 LPS 길이를 계산할 필요가 없다. 왜냐하면 그것은 정확히 같기 때문이다, 왼쪽에서의 대응되는 위치의 LPS 값으로서. 그리고 우리가 어떤 위치에서 LPS 길이 계산을 피하려는 이 사실은 Manacher 알고리즘을 선형으로 만든다.
왼쪽과 오른쪽 위치들이 중심위치 주변에서 대칭이 아닐 것이라는 상황에서, 우리는 팰린드롬을 찾기 위해 왼쪽과 오른쪽에서 문자들을 비교하지만, 여기에서 또는 알고리즘은 어떠한 비교를 피하려고 한다. 우리는 모든 이러한 시나리오들을 곧 보게 될 것이다.
더 나아가기 위해 몇 가지 용어들을 소개하자:
- centerPosition : 이것은 LPS 길이가 계산되는 위치이고, centerPosition에서의 LPS길이가 d라고 하자 (즉, L[centerPosition] = d)
- centerRightPosition : 이것은 centerPosition의 오른쪽에 있는 위치이고, centerPosition으로 부터 d 위치만큼 떨어져 있다 (즉, centerRightPosition = centerPosition+ d).
- centerLeftPosition : 이것은 centerPosition의 왼쪽에 있는 위치이고, centerPosition으루 부터 d만큼 떨어져 있다 (즉, centerLeftPosition = centerPosition - d).
- currentRightPosition : 이것은 centerPosition의 오른쪽에 있는 위치인데, LPS 길이가 아직 안알려져 있고, 계산되어져야 하는 위치이다.
- currentLeftPosition : 이것은 centerPosition의 왼쪽에 있는 위치인데, currentRightPosition과 같다 centerPosition - currentLeftPosition = currentRightPosition - centerPosition, currentLeftPosition = 2 * centerPosition - currentRightPosition
- i-left palindrome - centerPosition의 왼쪽의 팰린드롬 i 위치인데, 즉 currentLeftPosition이다.
- i-right palindrome - centerPosition의 오른쪽의 팰린드롬 i 위치인데, 즉, currentRightPosition이다.
- center palindrome - centerPosition의 팰린드롬이다.
우리가 LPS 길이가 알려져있는 centerPosition에 있을 때, 그러고나서 우리는 또한 centerPosition보다 더 작은 모든 위치의 LPS 길이를 알고있다. centerPosition에서 LPS 길이가 d라고 하자. 즉, L[centerPosition] = d이다.
그것은 centerPosition - d와 centerPosition + d 사이의 부분문자열이 팰린드롬이라는 것이다. 이제 우리는 centerPosition보다 더 큰 위치의 LPS 길이를 계산하기위해 진행한다. 우리가 currentRightPosition에(> centerPosition) 있다고 하자, 거기에서 우리는 LPS 길이를 찾을 필요가 있다. 이것에 대해, 우리는 이미 계산된 currentLeftPosition의 LPS 길이를 본다.
만약 currentLeftPosition의 LPS 길이가 "centerRightPosition - currentRightPosition"보다 작다면, 그러면 currentRightPosition의 LPS 길이는, currentLeftPosition의 LPS 길이와 같을 것이다. 그래서 L[currentRightPosition] = L[currentLeftPosition]인데, 만약 L[currentLeftPosition] < centerRightPosition - currentRightPosition이면. 이것은 Case 1이다.
"abababa" 문자열의 아래 시나리오를 고려해보자.
우리는 L[7] = 7인 위치 7까지의 LPS 길이를 계산했다. 만약 우리가 위치 7을 centerPosition을 고려한다면, 그러면 centerLeftPosition은 0이 되고, centerRightPosition은 14가 될 것이다. 이제 우리는 centerPosition의 오른쪽에 있는 다른 위치들의 LPS 길이를 계산할 필요가 있다.
currentRightPosition = 8에 대해, currentLeftPosition은 6이고, L[currentLeftPosition] = 0이고, 또한 centerRightPosition - currentRightPosition = 14 - 8 = 6이다.
case 1이 여기에서 적용되고, 그래서 L[currentRightPosition] = L[8] = 0이다.
case 1은 위치 10과 12에도 적용된다. 그래서,
L[10] = L[4] = 0
L[12] = L[2] = 0 이다.
만약 우리가 위치 9를 본다면, 그러고나서:
currentRightPosition = 9
currentLeftPosition = 2 * centerPosition - currentRightPosition = 2 * 7 - 9 = 5
centerRightPosition - currentRightPosition = 14 - 9 = 5
여기에서 L[currentLeftPosition] = centerRightPosition - currentRightPosition이고, 그래서 Case 1은 적용이 되지 않는다. 또한 centerRightPosition이 문자열의 맨 끝 위치에 있다는 것에 주목해라. 그것은 center palindrome이 input string의 suffix라는 것을의미한다. 그 경우에, L[currentRightPosition] = L[currentLeftPosition]이다. 이것이 Case 2이다.
Case 2는 위치 9, 11, 13 과 14에 적용된다. 그래서:
L[9] = L[5] = 5
L[11] = L[3] =3
L[13] = L[1] = 1
L[14] = L[0] = 0
Case 1과 Case 2에서 무엇이 일어나고 있는가? 이것은 palindromic symmetric property를 활용하는 것이고, 어떤 문자 매칭없이, 그것은 새로운 위치의 LPS 길이를 찾고있다.
더 큰 길이의 팰린드롬이 그것의 center의 left side에 중심을 둔 더 작은 length palindrome을 포함할 때, 그러면 symmetric property를 기반으로, 또 다른 같은 더 작은 팰린드롬이 더 큰 팰린드롬 센터의 오른쪽에 중심에 있을 것이다. 만약 left side smaller palindrome이 더 큰 palindrome의 prefix가 아니라면, 그러면 Case 1이 적용되고, 그것이 prefix이고, 더 큰 팰린드롬이 input string 그 자체의 suffix라면, 그러면 Case 2가 적용된다.
current center의 오른쪽 (i-right palindrome)에 위치한 가장 긴 팰린드롬 i 위치는 current center의 왼쪽에 위치한 가장 긴 palindrom i 위치만큼 길다 (i-left palindrome), 만약 그 i-left palindrome이 current center 주변의 완전히 longest palindrome 안에포함되고, 그 i-left palindrome이 center palindrome의 prefix가 아니라면(Case 1) 또는 (즉, i-left palindrome이 center palindrome의 prefix일 때), 만약 그 center palindrome이 전체 문자열의 suffix라면 (case 2).
Case 1과 Case2에서, i-right palindrome은 대응되는 i-left palindrome 이상으로 확장될 수 없다 (너는 왜 그것이 더 확장할 수 없는지시각화 할 수 있는가?), 그래서 i-right 팰린드롬의 LPS 길이는 정확히 i-left palindrome의 LPS길이와 정확히 같다.
댓글 없음:
댓글 쓰기