C++로 문자열에 짝수 길이 회문 부분 문자열이 존재하는지 확인하는 방법

소문자로만 이루어진 문자열이 하나 주어졌다고 가정해 보겠습니다. 우리의 과제는 주어진 문자열 안에 짝수 길이를 가진 회문(palindrome) 부분 문자열이 존재하는지 확인하는 것입니다. 존재한다면 1(true)을 반환하고, 그렇지 않다면 0(false)을 반환합니다.

예를 들어 입력이 "afternoon"이라면 출력은 true가 됩니다. "afternoon"에는 "oo"처럼 짝수 길이의 회문이 포함되어 있기 때문입니다.

핵심 아이디어

짝수 길이의 회문은 반드시 서로 같은 두 문자가 인접해 있는 구간을 포함합니다. 짝수 길이 회문은 중앙을 기준으로 좌우 대칭인데, 중앙에 위치한 두 문자는 항상 서로 같아야 하기 때문입니다. 따라서 모든 부분 문자열을 일일이 검사할 필요 없이, 인접한 두 문자가 같은 경우가 하나라도 존재하는지만 확인하면 됩니다.

알고리즘 단계

x := 0부터 시작하여 x가 문자열 길이 - 1보다 작을 동안 x를 1씩 증가시키며 반복합니다.
string[x]와 string[x + 1]이 같으면 true를 반환합니다.
반복이 끝날 때까지 같은 인접 문자 쌍을 찾지 못했다면 false를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드 (C++)

다음 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
bool solve(string string) {
    for (int x = 0; x < string.length() - 1; x++) {
        if (string[x] == string[x + 1])
            return true;
    }
    return false;
}
int main() {
    cout<<solve("afternoon") <<endl;
}

입력

"afternoon"