src/string/mp.hpp

• View this file on GitHub
• Last update: 2020-05-08 21:35:33+09:00
• Include: #include "src/string/mp.hpp"

Code

template <class S> V<int> mp(const S& s) {
    int n = int(s.size());
    V<int> r(n + 1);
    r[0] = -1;
    for (int i = 0, j = -1; i < n; i++) {
        while (j >= 0 && s[i] != s[j]) j = r[j];
        j++;
        r[i + 1] = j;
    }
    return r;
}

#line 1 "src/string/mp.hpp"
template <class S> V<int> mp(const S& s) {
    int n = int(s.size());
    V<int> r(n + 1);
    r[0] = -1;
    for (int i = 0, j = -1; i < n; i++) {
        while (j >= 0 && s[i] != s[j]) j = r[j];
        j++;
        r[i + 1] = j;
    }
    return r;
}

Back to top page