最長共通接頭辞(Z-algorithm)

このアルゴリズムの実装には、snukeさんの解説及び Senさんの解説 を大変参考にさせていただきました。

    
//SとS.substr(i,|S|-i)(i=0~|S|-1)の最長共通接頭辞の長さを格納した配列を返す
vector<long long> Z_algorithm(string S)
{
    long long siz = S.size();
    vector<long long> ret(siz);
    long long pre = 0;
    for (long long i = 1; i < siz; i++)
    {
        //計算済みの最長共通接頭辞に完全に覆われる
        if (i + ret[i - pre] < pre + ret[pre])
            ret[i] = ret[i - pre];
        //はみ出すorそもそもかぶらない場合
        else
        {
            //覆われている部分の長さ(かぶらない場合は0)
            long long j = max(0ll, pre + ret[pre] - i);
            //愚直にチェック
            while ((i + j) < siz && S[j] == S[i + j])
                j++;
            ret[i] = j;
            //鋳型となる最長共通接頭辞を変更する
            pre = i;
        }
    }
    //先頭はイレギュラーなので別に求める
    ret[0] = siz;
    return ret;
}
© 2020 kacho65535