【C++】文字列に偶数長の回文部分文字列が含まれているか判定する方法

小文字の英字のみで構成された文字列が与えられたとします。この文字列の中に、「回文」かつ「偶数の長さ」を満たす部分文字列が存在するかどうかを判定し、存在する場合は 1 を、存在しない場合は 0 を返すのが課題です。

例えば、入力が "afternoon" の場合、出力は 1(true)になります。「oo」という長さ 2 の回文部分文字列が含まれているためです。

解法のポイント

この問題は、実は隣り合う文字を比較するだけで解くことができます。

偶数長の回文では、中央に位置する 2 文字が必ず同じ文字になります。したがって、偶数長の回文が存在するならば、文字列内のどこかに「同じ文字が隣接している箇所」が必ず存在します。逆に言えば、隣接する同じ文字が 1 組も存在しなければ、偶数長の回文も存在しないことになります。

アルゴリズムの手順

• x を 0 から(文字列の長さ − 2)まで 1 ずつ増やしながら、以下を繰り返します。
  • string[x] と string[x + 1] が同じ文字であれば、true を返します。
• ループが終了するまで見つからなければ、false を返します。

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"

出力

1

計算量

文字列を一度走査するだけなので、時間計算量は O(n)、追加のメモリは不要で空間計算量は O(1) となります。非常にシンプルかつ効率的な解法です。