C++で基準文字列の文字順に従って文字列の配列をソートする方法

問題の概要

文字列の配列と、ソートの基準となるもう一つの文字列が与えられているとします。基準文字列に含まれる文字の出現順序を「独自のアルファベット順」とみなし、その順序に従って文字列の配列を並べ替えます。ここでは、配列内の文字列も基準文字列もすべて小文字で構成されているものと仮定します。

例えば、文字列の配列が ["hello", "programming", "science", "computer", "india"]、基準文字列が "pigvxbskyhqzelutoacfjrndmw" である場合、ソート後の出力は ["programming", "india", "science", "hello", "computer"] となります。

アプローチ

考え方はシンプルです。手順は以下の通りです。

1. 基準文字列を先頭から走査し、各文字をキー、そのインデックス（出現位置）を値としてハッシュマップ（unordered_map）に格納します。
2. ソート時には、通常のASCIIコード順ではなく、このマップに登録された優先度に基づいて文字列同士を比較します。
3. マップ内で各文字に対応付けられた値を比較し、文字 c1 が c2 より先に出現する場合は c1 < c2 と判断します。
4. 先頭から順に比較していき、すべての文字が一致した場合は、より短い文字列を先に配置します。

C++による実装例

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<char, int> char_map;

bool compare(string c1, string c2) {
    for (int i = 0; i < min(c1.size(), c2.size()); i++) {
        if (char_map[c1[i]] == char_map[c2[i]])
            continue;
        return char_map[c1[i]] < char_map[c2[i]];
    }
    return c1.size() < c2.size();
}

int main() {
    string str = "pigvxbskyhqzelutoacfjrndmw";
    vector<string> v{ "hello", "programming", "science", "computer", "india" };

    char_map.clear();
    for (int i = 0; i < str.size(); i++)
        char_map[str[i]] = i;

    sort(v.begin(), v.end(), compare);

    // ソート後の文字列を出力
    for (auto x : v)
        cout << x << " ";
}

出力結果

programming india science hello computer

処理のポイントと計算量

この実装では、std::sort にカスタム比較関数 compare を渡すことで、独自の文字順序を実現しています。比較関数内では、2つの文字列を先頭から1文字ずつ照合し、初めて異なる文字が見つかった時点でマップ上の優先度の大小を返します。

計算量について見てみましょう。文字数を n、文字列の本数を m、各文字列の平均的な長さを L とすると、マップの構築に O(n)、ソート部分は比較ごとに最大 O(L) かかるため、全体の計算量は O(n + m·L·log m) となります。ハッシュマップにより各文字の参照は O(1) で行えるため、非常に効率的な手法です。