[LPS] Longest Palindrome Substring / Subsequence

<문제>

입력으로 문자열이 들어온다.

문자열의 substring / subsequence중 Palindrome을 만족하는 문자열의 최대길이를 구해야한다.

결론적으로 subsequence는 O(N^2), substring은 O(N)의 시간복잡도를 갖는다. 그 이유에 대해서 알아보자.

 

※ N = 문자열의 길이

※ 문자열은 0부터 n-1의 인덱스를 갖는다. 

 

<substring>

1. 가장 먼저 떠올릴만한 방법은 (L, R)을 브루트포스로 구성하는 방법이다.

L의 범위는 0부터 n-2까지, R의 범위는 L+1부터 n-1까지 돌려준다. 여기에 O(n^2)의 시간이 소요된다.

이후 팰린드롬에 대한 판별은 구성된 문자열의 길이 M만큼의 시간이 소요된다.

M은 1~N의 값을 갖기에, O(N^3)의 시간복잡도를 갖는것으로 생각할 수 있다.

더 정확히 계산하면 1/4 * N^3정도의 연산횟수를 갖을 것 같다.

 

2. 이를 DP를 사용해서 O(N^2)까지 끌어내릴 수 있다. 아래의 문제가 DP를 사용한 최적화를 요구한다.

https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

 

3. 이를 더 개선해볼 수 있다. 알고리즘의 이름은 Manacher's algorithm이다. 

아래의 문제가 이를 요구한다.

https://www.acmicpc.net/problem/13275

13275번: 가장 긴 팰린드롬 부분 문자열

N의 길이의 문자열이 들어온다고 생각해보자. 이를 s[]에 저장하고, 배열하나를 추가로 생성해, 아래와 같이 구성한다.

a[i] = i번째 문자를 중심으로, 팰린드롬이 성립하는 반경

가령, 입력이 "121123"이면 a[i]={0, 1, 0, 0, 0, 0}인 셈이다.

a[i]의 최대값은 1, 이를통해 현재로선 최적해 3이라는 결론을 내릴 수 있지만, "2112"에 대한 판별이 불가능하다.

그렇기 위해 입력을 다음과 같이 변형해준다. 조금 간단한 예시로 "11"이 들어온다고 보자

input : "11" , s[] = "|1|1|"

s의 길이는 2(숫자)+3(' | ') = 5. 이때 a[i] = {0, 1, 2, 1, 0}이 된다. 

input이 "2112" 이면 s[] = "|2|1|1|2|, a[i] = {0, 1, 0, 1, 4, 1, 0, 1, 0}이다.

 그렇기에 입력되는 문자열의 시작과 끝, 사이에 임의의 문자를 삽입, 이후 a[]를 구성하면

우리가 찾는 정답은 a[]의 최대값이 된다.

 

이제 a[]를 채우는 데에 어느정도의 시간이 걸리느냐에 초점을 맞추어야 하는데...

아래의 Runtime 부분을 읽어보자. 2중 반복문으로 구성되어 있고, 큰 반복문은 명백한 O(N), 

작은 반복문의 최대 연산횟수는 N+N/2를 넘기지 않아 최종적인 시간복잡도가 

O(N+N+N/2) = O(N)이 나온다.

https://en.wikipedia.org/wiki/Longest_palindromic_substring

Longest palindromic substring - Wikipedia

<subsequence>

1. 역시나 브루트포스부터 시작해보자.

어떠한 문자열 s[]가 주어지고, 이 문자열을 선택하거나 선택하지 않아서 만들어진 subsequence의 개수는,

2^N개 존재한다. N이 5일때, 선택된 수열의 종류는 00000~11111까지의 2진수처럼 표현이 가능하다는것을 상기시켜 이해해도 좋겠다.

즉, subsequence의 개수는 2^N개 존재한다.

이들을 각각 팰린드롬인지를 판별하는데에 소요되는 시간은 O(M). M은 선택된 문자의 길이다.

역시 M의 범위가 1~N이고, 그렇기에 시간복잡도는 O(2^N * N)정도인데,

2^N에 비해서 N은 너무 작은 수이기에 사실상 O(2^N)이다.

 

2. 이를 DP를 사용해 최적화해보자.

2차원 DP를 생성하고, 이를 다음과 같이 구성한다.

DP[i][j] = 구간 (i,j)의 subsequence의 최적해

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAX = 100 + 1;
 
char s[MAX] = "ABDEBA";
int n, dp[MAX][MAX];
int main(void) {
    int i, len, L, R;
    n = strlen(s);
    for (i = 0; i < n; i++)
        dp[i][i] = 1;
    for (len = 2; len <= n; len++) {
        for (L = 0; L < n - len + 1; L++) {
            R = L + len - 1;
            if (s[L] == s[R]) {
                if (len == 2) {
                    dp[L][R] = 2;
                }
                else {
                    dp[L][R] = dp[L + 1][R - 1] + 2;
                }
            }
            else dp[L][R] = max(dp[L][R - 1], dp[L + 1][R]);
        }
    }
    printf("answer : %d\n", dp[0][n - 1]);
    return 0;
}

 

시간복잡도는 O(N^2), 이 역시 상당히 최적화가 되었다.

<결론>

Longest palindrome subsequnce : O(N^2)

Longest palindrome substring : O(N)