C++で複数の文字列から最長共通プレフィックス（接頭辞）を見つけるプログラム

本記事では、複数の文字列が与えられたときに、それらすべてに共通する最長の接頭辞（プレフィックス）を見つけるC++プログラムについて解説します。この手法は、ルーティングテーブルの検索やファイルパスの比較など、さまざまな場面で応用される基本的なアルゴリズムです。

アルゴリズムの考え方

基本的なアプローチはシンプルです。まず最初の文字列を仮の共通接頭辞とし、残りの文字列と順番に照合していきます。照合のたびに共通部分だけを取り出していくことで、最終的にすべての文字列に共通する最長の接頭辞が得られます。

手順1：2つの文字列間の一致する接頭辞を求める（matchedPrefixtill）

Begin
   文字列 s1 と s2 を受け取る
   n1 = 文字列 s1 の長さを格納
   n2 = 文字列 s2 の長さを格納
   for i = 0, j = 0; i <= n1 - 1 かつ j <= n2 - 1 の間繰り返す
      if s1[i] != s2[j]
         ループを抜ける
      result.push_back(s1[i])
   return result
End

手順2：文字列配列全体から最長の一致接頭辞を求める（matchedPrefix）

Begin
   function matchedPrefix(): 配列内の文字列から最長の一致接頭辞を返す
   pre = 先頭の文字列で初期化
   for i = 1 to n - 1
      pre = matchedPrefixtill(pre, a[i])
   return pre
End

C++による実装例

以下は、上記のアルゴリズムを実際に実装したサンプルコードです。

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

// 2つの文字列 s1 と s2 の間で一致する接頭辞を求める関数
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<<"最長の共通接頭辞が見つかりました - "<<res.c_str();
    else
        cout<<"一致する接頭辞はありません";
    return (0);
}

実行結果

最長の共通接頭辞が見つかりました - Tutor

処理の流れのポイント

• 初期化： 配列の先頭要素「Tutorialspoint」を仮の共通接頭辞として設定します。
• 逐次照合： 「Tutor」と比較すると「Tutor」が一致し、次に「Tutorials」と比較しても「Tutor」が維持されます。
• 計算量： 各照合は最短の文字列長に比例するため、全体として効率的に動作します。

このように、単純なループ処理を組み合わせるだけで、複数の文字列から共通する最長の接頭辞を簡単に求めることができます。共通部分が存在しない場合は空文字列が返されるため、その判定も容易です。