C++で文字列が部分文字列の繰り返しから構成できるか判定する方法

空でない文字列が与えられます。この文字列が、ある部分文字列を複数回連結することによって構成できるかどうかを判定するのが課題です。文字列は小文字の英字のみで構成され、長さは10,000を超えないものとします。

たとえば、入力が "abaabaaba" の場合、答えは true になります。これは「aba」という部分文字列を3回繰り返すことで作られているためです。一方、「abac」のような文字列は同一の部分文字列の繰り返しでは構成できないため、false となります。

アルゴリズムの考え方

この問題は、KMP法（Knuth–Morris–Pratt法）で使われる「失敗関数（failure function）」の考え方を応用すると効率的に解けます。失敗関数とは、各位置 i について「先頭から i 文字目までの部分文字列において、接頭辞と接尾辞が一致する最大の長さ」を記録した配列です。

文字列全体に対する失敗関数の値を L とすると、候補となる周期の長さは n − L になります。ここで n が (n − L) で割り切れる場合、その文字列は長さ (n − L) の部分文字列の繰り返しで構成されていると判断できます。計算量は O(n) であり、非常に高速です。

解決手順

• 動的計画法（KMPの失敗関数）のアプローチを採用します。
• サイズ n の配列 dp を定義します（n は文字列の長さ）。
• i := 1、j := 0 で初期化します。
• i < n の間、以下を繰り返します。
  • s[i] == s[j] の場合：dp[i] := j + 1 とし、i と j をそれぞれ1増やします。
  • それ以外の場合：
    • j > 0 ならば、j := dp[j − 1] とします。
    • j == 0 ならば、dp[i] := 0 として i を1増やします。
• ループ終了後、dp[n − 1] が 0 ではなく、かつ n % (n − dp[n − 1]) == 0 が成立すれば true を返します。
• それ以外の場合は false を返します。

実装例

以下にC++による実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    void printVector(vector<int> v){
        for(int i = 0; i < v.size(); i++) cout << v[i] << " ";
        cout << endl;
    }
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> dp(n);
        int i = 1;
        int j = 0;
        while(i < n){
            if(s[i] == s[j]){
                dp[i] = j + 1;
                i++;
                j++;
            } else {
                if(j > 0){
                    j = dp[j - 1];
                } else {
                    dp[i] = 0;
                    i++;
                }
            }
        }
        return dp[n - 1] && n % (n - dp[n - 1]) == 0;
    }
};
main(){
    Solution ob;
    string res = (ob.repeatedSubstringPattern("abaabaaba")) ? "true" : "false";
    cout << res;
}

入力

"abaabaaba"

出力

true