C++でメタ文字列を判定する方法（1箇所の入れ替えで2つの文字列が一致するか確認する）

メタ文字列とは？

この記事では、2つの文字列が「メタ文字列」であるかどうかを判定する方法を解説します。メタ文字列とは、互いに非常によく似た文字列のことで、片方の文字列内で2つの文字を入れ替えるともう片方の文字列と完全に一致するような関係を指します。例えば、「HELLO」と「OELLH」という2つの文字列は、HとOを入れ替えることで一致するため、メタ文字列です。

判定の手順

2つの文字列がメタ文字列かどうかを確認するには、以下の手順に従います。

• 両方の文字列の長さが異なる場合は、false を返す。
• 長さが同じ場合は、一致しない文字の数を数え、その位置（インデックス）も記録する。
• 不一致の文字数が2より大きい場合は、false を返す。
• それ以外の場合は、該当する文字を入れ替えて再度比較し、2つの文字列が一致すれば true、一致しなければ false を返す。

C++による実装例

#include <iostream>
using namespace std;
bool areTheyMetaString(string s1, string s2) {
    int s1_len = s1.length();
    int s2_len = s2.length();
    if (s1_len != s2_len)
    return false;
    int prev = -1, curr = -1;
    int count = 0;
    for (int i=0; i<s1_len; i++) {
        if (s1[i] != s2[i]) {
            count++; // 一致しない文字の数
            if (count > 2)
            return false;
            prev = curr;
            curr = i;
        }
    }
    return (count == 2 && s1[prev] == s2[curr] && s1[curr] == s2[prev]);
}
int main() {
    string s1 = "HELLO", s2 = "OELLH";
    if(areTheyMetaString(s1, s2)){
        cout << "Meta Strings";
    } else {
        cout << "Not Meta Strings";
    }
}

実行結果

Meta Strings

コードのポイント

このアルゴリズムでは、不一致の文字は最大でも2つまでしか許容されません。また、単に不一致が2箇所あるだけでなく、s1[prev] == s2[curr] かつ s1[curr] == s2[prev] という条件、つまり互いの文字が交差して一致している必要があります。これにより、実際に1回の入れ替えで2つの文字列が等しくなることが保証されます。計算量は文字列の長さを n とすると O(n) であり、非常に効率的な判定方法です。