C++で文字列の集合に共通する最長サブシーケンス（共通接頭辞）を見つける方法

本記事では、複数のシーケンス（文字列）の集合の中から、すべてのシーケンスに共通する最長のサブシーケンス（共通接頭辞）を見つけるC++プログラムについて解説します。この手法は、先頭から順に文字を比較していくことで、共通部分を効率的に抽出できる点が特徴です。

アルゴリズム

このプログラムは、2つの文字列間で一致する接頭辞を求める関数と、文字列配列全体にその結果を順次適用していく関数の、2段階構成になっています。

開始
文字列の配列を入力として受け取る。
関数 matchedPrefixtill()：文字列 s1 と s2 の間で一致する接頭辞を求める：
    n1 = 文字列 s1 の長さを格納
    n2 = 文字列 s2 の長さを格納
    i = 0, j = 0 から「i <= n1 - 1 かつ j <= n2 - 1」の間ループ
        もし s1[i] != s2[j] ならば
            break（ループを抜ける）
        result.push_back(s1[i])
    result を返す
終了

開始
関数 matchedPrefix()：文字列配列から最も長く一致する接頭辞を返す：
    i = 1 から n - 1 までループ
        pre = matchedPrefixtill(pre, a[i])
    pre を返す
終了

サンプルコード

#include<bits/stdc++.h>
using namespace std;

string matchedPrefixtill(string s1, string s2) {
    string res;
    int n1 = s1.length(); //文字列s1の長さを格納
    int n2 = s2.length(); //文字列s2の長さを格納
    for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) {
        if (s1[i] != s2[j])
            break;
        res.push_back(s1[i]);
    }
    return (res);
}
string matchedPrefix (string a[], int n) {
    string pre = a[0];
    for (int i = 1; i <= n - 1; i++)
    pre = matchedPrefixtill(pre, a[i]);
    return (pre);
}
int main() {
    string a[] = {"Tutorialspoint", "Tutor", "Tutorials"}; //入力データ
    int n = sizeof(a) / sizeof(a[0]);
    string res = matchedPrefix(a, n);
    if (res.length())
        cout<<"Longest common subsequence is matched - "<<res.c_str();
    else
        cout<<"No matched prefix";
    return (0);
}

出力結果

Longest common subsequence is matched - Tutor

プログラムの解説

このプログラムは以下の手順で動作します。

1. matchedPrefixtill() 関数：2つの文字列 s1 と s2 を受け取り、先頭の文字から順に1文字ずつ比較します。異なる文字が現れた時点でループを終了し、それまでに一致した文字列を返します。
2. matchedPrefix() 関数：最初の文字列を初期値として設定し、残りの文字列に対して matchedPrefixtill() を順番に適用していきます。これにより、配列内のすべての文字列に共通する最長の接頭辞が得られます。
3. main() 関数：3つの文字列「Tutorialspoint」「Tutor」「Tutorials」を入力とし、結果を出力します。共通部分が存在しない場合は「No matched prefix」と表示されます。

上記の例では、「Tutorialspoint」「Tutor」「Tutorials」の3つの文字列すべてに共通する部分は先頭の「Tutor」であるため、これが出力されます。

なお、このアルゴリズムの計算量は、入力文字列全体の文字数に比例する O(S) となります。各文字は高々数回しか走査されないため、文字列の数や長さが増えても非常に効率的に動作します。