C++で最長共通接頭辞を得るための最小シフト回数を求めるアルゴリズム

問題概要

同じ長さを持つ2つの文字列AとBが与えられたとします。1回のシフト操作によって、文字列Bを1文字ずつ回転（ローテート）できるものとします。このとき、AとBの間で最長の共通接頭辞（プレフィックス）が得られるようにするために必要な最小のシフト回数を求めるのが本問題です。

たとえば、A = “programminglanguage”、B = “computerprogramming” の場合、Bを8回シフトすれば共通接頭辞 “programming” が得られるため、最小シフト回数は8、接頭辞は “programming” となります。

アルゴリズムの考え方

各シフト量について個別に接頭辞を比較する方法は非常に非効率です。そこで、文字列Bをそれ自身と連結して B = B + B とします。こうすると、あらゆるシフトの結果が連結後のBの部分文字列として必ず現れるため、シフトごとに調べ直す必要がなくなります。

次に、連結後の文字列Bの中から、Aの接頭辞と最も長く一致する部分を探します。その一致部分の開始位置こそが、求めるべき最小シフト回数に相当します。文字列検索にはKMP法（Knuth–Morris–Pratt法）を採用することで、線形時間O(n)で効率よく解くことができます。

C++での実装例

#include<iostream>
using namespace std;
void KhuthMorrisPatt(int m, int n, string B, string A) {
    int pos = 0, len = 0;
    int p[m + 1];
    int k = 0;
    p[1] = 0;
    for (int i = 2; i <= n; i++) {
        while (k > 0 && A[k] != A[i - 1])
            k = p[k];
        if (A[k] == A[i - 1])
            ++k;
            p[i] = k;
        }
        for (int j = 0, i = 0; i < m; i++) {
            while (j > 0 && A[j] != B[i])
                j = p[j];
            if (A[j] == B[i])
                j++;
            if (j > len) {
                len = j;
                pos = i - j + 1;
            }
    }
    cout << "Shift = " << pos << endl;
    cout << "Prefix = " << A.substr(0, len);
}
int main() {
    string A = "programminglanguage";
    string B = "computerprogramming";
    int n = A.size();
    B = B + B;
    KhuthMorrisPatt(2 * n, n, B, A);
}

実行結果

Shift = 8
Prefix = programming

コードの解説

KhuthMorrisPatt 関数では、まずKMP法の前処理として、パターン文字列Aに対する失敗関数（LPS配列）である配列 p を構築します。これにより、照合中に不一致が発生した場合でも、比較位置を効率的に巻き戻すことができ、無駄な再比較を回避できます。

続いて、連結済みの文字列B（長さは元の2倍）を先頭から走査し、Aとの一致文字数 j を追跡していきます。一致長がそれまでの最大値 len を更新するたびに、その開始位置 i - j + 1 を pos として記録します。走査が完了した時点で、pos が最小シフト回数、A.substr(0, len) が最長共通接頭辞を表します。

この手法により、全シフトパターンを素朴に試すO(n²)アプローチと比べて大幅に高速化でき、長い文字列に対しても実用的な性能を発揮します。