C++で最長共通部分文字列を出力するプログラムの解説

このチュートリアルでは、C++を用いて最長共通部分文字列（Longest Common Substring）を求めて出力するプログラムについて詳しく解説します。

最長共通部分文字列とは

2つの文字列AとBが与えられたとき、両方の文字列に共通して現れる最も長い「連続した」文字の並び（部分文字列）を見つけ出すのがこの問題の目的です。

例えば、「helloworld」と「worldbook」という2つの文字列が与えられた場合、共通する最長の部分文字列は「world」となります。

アルゴリズムの考え方（動的計画法）

この問題は動的計画法（DP）を使うことで効率的に解くことができます。手順は以下の通りです。

• 2次元テーブル longest[i][j] を作成し、文字列Xのi文字目までと文字列Yのj文字目までの間で共通する部分文字列の長さを記録します。
• X[i-1] と Y[j-1] が一致する場合：longest[i][j] = longest[i-1][j-1] + 1
• 一致しない場合：0 を設定します（部分文字列は連続している必要があるため）。
• テーブル内の最大値とその位置を記録しておき、後からその位置を遡ることで実際の部分文字列を復元します。

C++での実装例

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
void print_lstring(char* X, char* Y, int m, int n){
    int longest[m + 1][n + 1];
    int len = 0;
    int row, col;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                longest[i][j] = 0;
            else if (X[i - 1] == Y[j - 1]) {
                longest[i][j] = longest[i - 1][j - 1] + 1;
                if (len < longest[i][j]) {
                    len = longest[i][j];
                    row = i;
                    col = j;
                }
            }
            else
                longest[i][j] = 0;
        }
    }
    if (len == 0) {
        cout << "There exists no common substring";
        return;
    }
    char* final_str = (char*)malloc((len + 1) * sizeof(char));
    while (longest[row][col] != 0) {
        final_str[--len] = X[row - 1];
        row--;
        col--;
    }
    cout << final_str;
}
int main(){
    char X[] = "helloworld";
    char Y[] = "worldbook";
    int m = strlen(X);
    int n = strlen(Y);
    print_lstring(X, Y, m, n);
    return 0;
}

出力結果

world

コードのポイント

• テーブルの初期化： iまたはjが0の場合（どちらかの文字列が空の場合）、共通部分文字列の長さは0になります。
• 最大値の追跡： テーブルを埋めながら最大値 len と、その位置（row, col）を記録します。
• 文字列の復元： 記録した位置から左上方向へ遡りながら、一致した文字を取り出すことで結果の文字列を構築します。
• 共通部分がない場合： len が0のままなら、共通部分文字列が存在しない旨のメッセージを表示します。

計算量について

このアルゴリズムの時間計算量・空間計算量はともに O(m × n) です（m、nはそれぞれの文字列の長さ）。すべての組み合わせを総当たりで調べる素朴な手法と比べ、動的計画法を用いることで大幅に効率化できる点が大きなメリットです。