String/MP.cpp

Back to top page

• category: String
• View this file on GitHub
  • Last commit date: 2020-05-14 17:59:14+09:00

Description

文字列 s について、部分文字列 s[1,i] の prefix と suffix がどこまで一致しているかを示す配列 a を求める。
計算量は O(|s|) 。

Code

//@docs Docs/MP.md
vector<int> MP(string &s) {
    int j = -1;
    int n = s.length();
    vector<int> a(n + 1);
    a[0] = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && s[i] != s[j]) {
            j = a[j];
        }
        j++;
        a[i + 1] = j;
    }
    return a;
}

#line 1 "String/MP.cpp"
//@docs Docs/MP.md
vector<int> MP(string &s) {
    int j = -1;
    int n = s.length();
    vector<int> a(n + 1);
    a[0] = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && s[i] != s[j]) {
            j = a[j];
        }
        j++;
        a[i + 1] = j;
    }
    return a;
}

Back to top page