C++でS1の接頭辞とS2の接尾辞を連結したときに回文となるインデックスiを見つける方法

概要

同じ長さの2つの文字列 S1 と S2 が与えられたとき、S1[0…i] と S2[i+1…n-1] をこの順で連結した結果が回文になるようなインデックス i を求めるのが本記事の課題です。条件を満たすインデックスが存在しない場合は -1 を出力します。

入力例1

S1 = "pqrsu", S2 = "wxyqp"

出力例1

1

このとき S1[0..1] = "pq"、S2[2..n-1] = "ypq" となります。

両者を連結した "pqyqp" は前後対称な文字列、つまり回文になっています。

入力例2

S1 = "pqrst", S2 = "qprqz"

出力例2

-1

どのようなインデックスで分割しても回文が成立しないため、-1 が出力されます。

アルゴリズムの考え方

• まず、0 から n(文字列の長さ)までループを回し、S1 の先頭から i 番目までの文字を別の文字列 S に順次コピーしていきます。
• 次に、一時用の文字列 temp を用意し、S2 のインデックス i+1 から末尾までの文字をコピーします。
• 最後に、連結した文字列(S + temp)が回文かどうかを判定し、回文であればその時点のインデックス i を答えとして返します。

C++での実装例

// C++による実装例
#include <bits/stdc++.h>
using namespace std;

// 文字列strが回文であればtrueを返す関数
bool isPalindrome(string str){
    int left = 0;
    int right = str.length() - 1;
    while (left < right) {
        if (str[left] != str[right])
            return false;
        left++;
        right--;
    }
    return true;
}

// 条件を満たすインデックスを返す関数
int getIndex(string S1, string S2, int n){
    string S = "";
    for (int i = 0; i < n; i++) {
        // S1のi番目までの文字をSにコピー
        S = S + S1[i];
        string temp = "";
        // S2のi+1番目以降の文字をすべてtempにコピー
        for (int j = i + 1; j < n; j++)
            temp += S2[j];
        // 連結した文字列が回文かどうかを判定
        if (isPalindrome(S + temp)) {
            return i;
        }
    }
    return -1;
}

// ドライバーコード
int main(){
    string S1 = "pqrsu", S2 = "wxyqp";
    int n = S1.length();
    cout << getIndex(S1, S2, n);
    return 0;
}

出力

1

計算量について

各インデックス i に対して文字列の構築と回文判定にそれぞれ O(n) の時間が必要となるため、全体の時間計算量は O(n²)、必要な空間計算量は O(n) となります。文字列長が十分に小さい場合はこの素直な手法で問題ありませんが、入力が大きくなる場合はより効率的なアルゴリズム(ローリングハッシュなど)の検討が有効です。