C++で回文を形成するための文字の配置位置を出力するプログラム

長さnの文字列strが与えられます。この文字列の各要素の位置を出力し、それらを並べ替えることで回文を形成できるようにします。回文が作れない場合は、画面に「No palindrome」というメッセージを出力します。

回文とは?

回文とは、前から読んでも後ろから読んでも同じになる単語や文字列のことです。例えば「MADAM」や「racecar」などが挙げられます。

ある文字列が回文かどうかを判定する一般的な方法は、元の文字列を逆順にしたものを別の文字列に保存し、両者を比較することです。両者が一致すれば、その文字列は回文であると判断できます。しかし本記事の問題では、回文の判定ではなく、与えられた文字列を並べ替えて回文を作るための配置(位置)を出力することが求められています。

例えば、文字列 str = "tinni" の場合、「intni」や「nitin」という回文を作ることができます。このとき、1から始まるインデックスで位置を出力すると、「2 3 1 4 5」または「3 2 1 5 4」のいずれかが結果として得られます。

入力例と出力例

Input: string str = "baa"
Output: 2 1 3
Input: string str = "tinni"
Output: 2 3 1 4 5

アルゴリズム

void printPalindromePos(string &str)
START
STEP 1: vector<int> pos[MAX] を宣言する
STEP 2: n に str の長さを代入して宣言する
STEP 3: i = 0 から i < n までループし、i を増加させる
    pos[str[i]].push_back(i+1)
ループ終了
STEP 4: oddCount = 0 を設定する
STEP 5: oddChar を宣言する
STEP 6: i = 0 から i < MAX までループする
    IF pos[i].size() % 2 != 0 THEN,
        oddCount を 1 増やす
        oddChar に i を設定する
    END IF
END FOR
STEP 7: IF oddCount > 1 THEN,
    「NO PALINDROME」を出力する
STEP 8: i = 0 から i < MAX までループする
    mid = pos[i].size()/2 を宣言する
    j = 0 から j < mid までループする
        pos[i][j] を出力する
    ループ終了
ループ終了
STEP 9: IF oddCount > 0 THEN,
    last = pos[oddChar].size() - 1 を宣言して設定する
    pos[oddChar][last] を出力する
    pos[oddChar].pop_back() を実行する
END IF
STEP 10: i = MAX-1 から i >= 0 まで逆順にループする
    count = pos[i].size() を宣言して設定する
    j = count/2 から j < count までループする
        pos[i][j] を出力する
STOP

アルゴリズムのポイント

• 各文字が出現する位置(1始まりのインデックス)を、文字ごとのvectorに格納します。
• 奇数回出現する文字の種類を数えます。回文に含めることができる奇数個の文字は高々1種類だけなので、2種類以上存在する場合は回文を作れません。
• まず各文字の前半分の位置を出力し、次に奇数個の文字(存在すれば)を中央に配置し、最後に残り半分の位置を逆順に出力します。これにより、回文の左半分・中央・右半分が構成されます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
// 最大文字数を定義
const int MAX = 256;
void printPalindromePos(string &str){
    // 与えられた文字列内のすべての文字の位置を挿入する
    vector<int> pos[MAX];
    int n = str.length();
    for (int i = 0; i < n; i++)
        pos[str[i]].push_back(i+1);
        /* 奇数個出現する要素の数を求める。計算量はO(n) */
    int oddCount = 0;
    char oddChar;
    for (int i=0; i<MAX; i++) {
        if (pos[i].size() % 2 != 0) {
            oddCount++;
            oddChar = i;
        }
    }
    /* 回文に含まれる奇数個の文字は1種類まで */
    if (oddCount > 1)
        cout << "NO PALINDROME";
    /* 回文の前半部分の位置を出力 */
    for (int i=0; i<MAX; i++){
        int mid = pos[i].size()/2;
        for (int j=0; j<mid; j++)
            cout << pos[i][j] << " ";
    }
    // 奇数個の文字を1つ中央に配置する
    if (oddCount > 0){
        int last = pos[oddChar].size() - 1;
        cout << pos[oddChar][last] << " ";
        pos[oddChar].pop_back();
    }
    /* 回文の後半部分の位置を出力 */
    for (int i=MAX-1; i>=0; i--){
        int count = pos[i].size();
        for (int j=count/2; j<count; j++)
        cout << pos[i][j] << " ";
    }
}
int main(){
    string s = "tinni";
    printPalindromePos(s);
    return 0;
}

出力

上記のプログラムを実行すると、以下の出力が生成されます。

2 3 1 4 5