mp法
(String/mp.hpp)

• View this file on GitHub
• Last update: 2024-07-06 20:37:29+09:00
• Include: #include "String/mp.hpp"

概要

mp法を行う。 参考:https://snuke.hatenablog.com/entry/2014/12/01/235807

関数

• vec<int> MP(string s)…mp法を行った配列mpを返す。 mp[i] := [0, i]の接頭辞と接尾辞の最大共通文字列であって、i+1未満の長さの物の長さ
  • 計算量 $O(|S|)$
• int shortest_run(vec<int> &mp, int i) …[0, i]の最小周期長。mpには、MPの返り値を渡す。
  • 計算量 $O(1)$

shortest_runの説明

長さが $n$ の文字列 $S$ について、次の命題が成立する。

Sが周期長kを持つ⇔Sと、Sをk文字右にずらした文字列の共通部分が一致する⇔S[0, n-k] = S[k, n]

また、次の命題も成立する

S[0, n-k] = S[k, n] ⇔ Sの最長共通文字列であって、n未満の長さの物の長さ >= n-k

合わせて、 Sが周期kを持つ ⇔ mp[n-1] >= n - k

これを、mp法の形式に合わせると、

S[0, i]が周期kを持つ ⇔ mp[i] >= i+1 - k

となって

S[0, i]の最小周期長 = i+1 - mp[i]

Code

vec<int> MP(string S) {
    int n = S.size();
    vec<int> res(n+1, -1);
    int j = -1;
    rep(i, 0, n) {
        while(j >= 0 && S[i] != S[j]) j = res[j];
        j++;
        res[i+1] = j;
    }
    res.erase(res.begin());
    return res;
}


int shortest_run(vec<int> &mp, int i) {
    return i + 1 - mp[i];
}
/*
@brief mp法
@docs doc/mp.md
*/

#line 1 "String/mp.hpp"
vec<int> MP(string S) {
    int n = S.size();
    vec<int> res(n+1, -1);
    int j = -1;
    rep(i, 0, n) {
        while(j >= 0 && S[i] != S[j]) j = res[j];
        j++;
        res[i+1] = j;
    }
    res.erase(res.begin());
    return res;
}


int shortest_run(vec<int> &mp, int i) {
    return i + 1 - mp[i];
}
/*
@brief mp法
@docs doc/mp.md
*/

Back to top page