[알고리즘] Palindrom Algorithm

Palindrom Algorithm이란 ?

 

Palindrom은 똑바로 읽어도 거꾸로 읽어도 같은 문자열을 의미한다.

따라서 Palindrom Algorithm은 문제에 주어진 문자열이 있을 때, 부분 문자열 중 Palindrom인
문자열을 찾는 알고리즘이다.

구현방법

1. 원하는 문자열을 가로축 세로축으로 이차원 행렬을 만든다.

2. 이차원 행렬의 중간 대각선은 자기 자신을 가리키는것임으로 1로 다 채워준다.

3. 문자열을 돌면서 앞뒤가 같으면 2로 표기한다.

4. 이제 2부터 이차원 행렬 반복문을 돌면서 밑 대각선에 0이 아닌 숫자가 존재하면 
   같은게 진행중이라는 뜻으로 그곳에 +2를 해가며 행렬을 완성한다. 
   만들어보면 처음 1로 채워준 대각선 기준 위쪽만 채워지고 대각선 밑쪽은 채워질 필요가 없다는 것을 알 수 있다.

5. 완성된 이차원 행렬에서 최대값을 찾아서 리턴해준다.

 

코드

string longestPalindrome(string s) {
        int str_length = s.length();
    std::vector<std::vector<int>> dp_table(str_length, std::vector<int>(str_length, 0));

    // 각 문자는 길이가 1인 팰린드롬이므로 dp_table을 초기화
    for (int idx = 0; idx < str_length; ++idx) {
        dp_table[idx][idx] = 1;
    }

    // 연속된 두 문자가 동일한 경우 처리
    for (int idx = 0; idx < str_length - 1; ++idx) {
        if (s[idx] == s[idx + 1]) {
            dp_table[idx][idx + 1] = 2;
        }
    }

    // 그 외의 경우 처리
    for (int idx = 2; idx < str_length; ++idx) {
        int row = 0;
        int col = idx;
        while (col < str_length) {
            if (s[row] == s[col] && dp_table[row + 1][col - 1] != 0) {
                dp_table[row][col] = dp_table[row + 1][col - 1] + 2;
            }
            ++row;
            ++col;
        }
    }

    //이차원 행렬에서 최댓값 찾는 코드
    int max_length = 0;
    int start_idx = 0;
    int end_idx = 0;
    for (int row = 0; row < str_length; ++row) {
        for (int col = 0; col < str_length; ++col) {
            int crnt_length = dp_table[row][col];
            if (max_length < crnt_length) {
                max_length = crnt_length;
                start_idx = row;
                end_idx = col;
            }
        }
    }

    return s.substr(start_idx, end_idx - start_idx + 1);
    }