부분 문자열 팰린드롬 판별 알고리즘

이번에는 문자열 처리과정에서 팰린드롬 처리에 관한 알고리즘을 소개하고자 한다.

문자열 내의 부분 문자열이 팰린드롬인지 확인해보는 알고리즘이다.

즉, String이 주어질 때 Substring이 Palindrome(회문)인지 알아보는 알고리즘이다.

사실 Manacher's Algorithm이라는 알고리즘이 존재하는데, 문자열 내에서 부분 문자열이 팰린드롬인지 O(n)에 확인하는 알고리즘이 있다.

이번에는 Manacher's 알고리즘보다는 복잡도면에서 상당히 밀리지만,

DP를 이용하여 O(n^2)의 복잡도로 문자열내 부분문자열 팰린드롬 확인을 해보려한다.

(보통 문제는 이 방법으로도 해결이 되니 알아두고 가면 좋을 듯 하다.)

바로 코드를 보며 분석을 통해 알고리즘을 이해해보자.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
char arr[2002];
bool DP[2002][2002];
 
int main()
{
    int n;
 
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
        scanf(" %c", &arr[i]);
 
    for (int i = 1; i <= n; i++)
        DP[i][i] = true;
 
    for (int i = 1; i <= n-1; i++)
        if (arr[i] == arr[i + 1])
            DP[i][i + 1] = true;
 
    // k칸 다음번째
    for (int k = 2; k <= n-1; k++)
    {
        // 1부터 ~ n - k 번째 까지
        for (int i = 1; i <= n - k; i++)
        {
            // i + k번째 칸
            int j = i + k;
            if (arr[i] == arr[j] && DP[i + 1][j - 1])
                DP[i][j] = true;
        }
    }
 
    int m;
    scanf("%d", &m);
 
    while (m--)
    {
        int start, end;
        scanf("%d %d", &start, &end);
 
        DP[start][end] ? printf("1\n") : printf("0\n");
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

소스코드 분석을 시작해보자.

우선 n을 입력 받고 1~n 배열에 문자를 하나씩 집어넣는 과정이 있다.

그 후 첫번째로 등장하는 for문에 대해 살펴보자.

for (int i = 1; i <= n; i++)
    DP[i][i] = true;
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

DP[i][i] = true의 의미는 다음과 같다.

-> i~i번째는 항상 팰린드롬이다.

     즉, 자기 자신은 항상 팰린드롬이라는 것이다.

두번째 for문에 대해 생각해보자.

for (int i = 1; i <= n - 1; i++)
    if (arr[i] == arr[i + 1])
        DP[i][i + 1] = true;
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

-> i와 i + 1번째 값이 같다면 i ~ i + 1번째는 항상 팰린드롬이다.

     예를들어 aa, bb같은 값들이 존재한다.

이제 아래의 이중 포문을 살펴보자.

    // k칸 다음번째
    for (int k = 2; k <= n-1; k++)
    {
        // 1부터 ~ n - k 번째 까지
        for (int i = 1; i <= n - k; i++)
        {
            // i + k번째 칸
            int j = i + k;
            if (arr[i] == arr[j] && DP[i + 1][j - 1])
                DP[i][j] = true;
        }
    }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

여기서 k, i, j의 동작 과정은 아래 그림과 같다.

k가 2일때 i, j, k의 상호 동작과정을 나타내는 그림이다.

즉, k는 i에서 몇칸 뛸지 보는 변수이고,

arr[i]와 arr[j]가 같은지 확인 한 후, 같다면 DP[i+1][j-1]이 이미 팰린드롬이었는지만 확인해주면

DP[i][j]도 팰린드롬인지 여부가 확인이 가능해지는 것이다.

시간 복잡도

눈대중으로 봐서 당연히 n^2이라고 느껴진다.

왜냐면 이중 포문에서 딱히 lgN으로 떨어지는 과정이 없기 때문이다.

이 코드의 core는 결국 2중 for문이고

그 내부에서 총 몇번 수행작업이 일어나는지 카운트를 해보면 다음과 같다.

1 3 6 10 15 21 ...

결국 계차수열이고 계차수열 내에서 등차수열이 일어나고 있기에 (n*(n+1))/2 공식이 적용되어

DP를 이용한 소스 코드는 O(n^2) 시간 복잡도를 가짐을 확인 할 수 있다.

사실상 이 방법을 이용하여

[10942번] 팰린드롬? :: https://www.acmicpc.net/problem/10942

문제를 해결 해 볼 수 있다.