C++で最も長い重複部分文字列を求めるアルゴリズム

問題の概要

文字列 S が与えられます。ここで、S の中に 2 回以上出現する連続する部分文字列（重複部分文字列）をすべて考えてみましょう。ただし、出現位置が互いに重なっても構いません。このとき、最も長い重複部分文字列を見つけるのが課題です。該当する部分文字列が存在しない場合は空文字列を返します。

なお、ローリングハッシュによる計算では値が巨大になるため、10⁹ + 7 を法（mod）として演算を行います。

例えば、入力が "ababbaba" の場合、出力は "bab" となります。

解き方のアプローチ

この問題は、二分探索とローリングハッシュ（Rabin–Karp 法）を組み合わせることで効率的に解けます。「長さ x の重複部分文字列が存在すれば、それより短い長さの重複も必ず存在する」という単調性があるため、重複部分文字列の長さについて二分探索が成立します。各長さ x の判定では、スライディングウィンドウでハッシュ値を更新しながら、同じハッシュ値を持つ開始位置を記録することで重複を検出します。

アルゴリズムの流れ

• m := 1e9 + 7（mod の値）
• 関数 add(a, b)：((a mod m) + (b mod m)) mod m を返す
• 関数 sub(a, b)：((a mod m) − (b mod m) + m) mod m を返す
• 関数 mul(a, b)：((a mod m) × (b mod m)) mod m を返す
• 配列 power を用意する（26 のべき乗を格納）
• 関数 ok(x, s)：長さ x の重複部分文字列が存在すればその文字列を、なければ空文字列を返す
  • x が 0 の場合は空文字列を返す
  • マップ hash を用意する
  • current := 0 と初期化
  • i := 0 から x − 1 まで繰り返し：current := add(mul(current, 26), s[i] − 'a') で先頭 x 文字のハッシュ値を計算
  • hash[current] := { 0 }（開始位置 0 を登録）
  • n := s のサイズ
  • i := x から n − 1 まで繰り返し：
    • current := sub(current, mul(power[x − 1], s[i − x] − 'a')) で窓の先頭文字の寄与を除去
    • current := add(mul(current, 26), s[i] − 'a') で新しい文字を追加（スライディングウィンドウ）
    • current が hash に既に存在する場合：
      • hash[current] 内の各開始位置 it について、s.substr(it, x) と s.substr(i − x + 1, x) が一致すれば、その部分文字列を返す（ハッシュ衝突の確認）
    • そうでなければ、hash[current] の末尾に i − x + 1 を追加
  • ループを抜けたら空文字列を返す
• メイン処理（longestDupSubstring）：
  • ret := 空文字列、n := S のサイズ
  • power := サイズ n・全要素 1 の配列とし、i = 1 から順に power[i] := mul(power[i − 1], 26) を計算
  • low := 0、high := n − 1 として二分探索を実行：
    • mid := low + (high − low) / 2
    • temp := ok(mid, S)
    • temp が空なら high := mid − 1（長さ mid の重複は存在しない）
    • 空でなければ、temp の方が長い場合に ret を更新し、low := mid + 1（より長い長さを試す）
  • ret を返す

C++ 実装例

以下の実装を見ると、理解がより深まるでしょう。

コード例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int m = 1e9 + 7;
   int add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   int sub(lli a, lli b){
      return ((a % m) - (b % m) + m) % m;
   }
   int mul(lli a, lli b){
      return ((a % m) * (b % m)) % m;
   }
   vector<int> power;
   string ok(int x, string s){
      if (x == 0)
      return "";
      unordered_map<int, vector<int> > hash;
      lli current = 0;
      for (int i = 0; i < x; i++) {
         current = add(mul(current, 26), s[i] - 'a');
      }
      hash[current] = vector<int>(1, 0);
      int n = s.size();
      for (int i = x; i < n; i++) {
         current = sub(current, mul(power[x - 1], s[i - x] -
         'a'));
         current = add(mul(current, 26), s[i] - 'a');
         if (hash.count(current)) {
            for (auto& it : hash[current]) {
               if (s.substr(it, x) == s.substr(i - x + 1, x)) {
                  return s.substr(it, x);
               }
            }
         } else {
            hash[current].push_back(i - x + 1);
         }
      }
      return "";
   }
   string longestDupSubstring(string S){
      string ret = "";
      int n = S.size();
      power = vector<int>(n, 1);
      for (int i = 1; i < n; i++) {
         power[i] = mul(power[i - 1], 26);
      }
      int low = 0;
      int high = n - 1;
      while (low <= high) {
         int mid = low + (high - low) / 2;
         string temp = ok(mid, S);
         if (temp.size() == 0) {
            high = mid - 1;
         } else {
            if (temp.size() > ret.size())
            ret = temp;
            low = mid + 1;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.longestDupSubstring("ababbaba"));
}

入力

"ababbaba"

出力

bab

まとめ

二分探索によって重複部分文字列の長さを絞り込み、各判定にはローリングハッシュを活用することで、時間計算量 O(n log n) で最長の重複部分文字列を求めることができます。また、ハッシュ値が一致した場合でも実際の文字列比較で確認しているため、ハッシュ衝突による誤判定を防げる点も重要なポイントです。