cp_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub downerkei/cp_library

:warning: string/lps_table.hpp

Code

template<typename VType>
vector<int> lps_table(const VType& s) {
    int n = s.size();
    vector<int> lps(n + 1);
    lps[0] = -1;
    int j = -1;
    for(int i = 0; i < n; i++) {
        while(j >= 0 && s[i] != s[j]) j = lps[j];
        j++;
        lps[i + 1] = j;
    }
    return lps;
}
#line 1 "string/lps_table.hpp"
template<typename VType>
vector<int> lps_table(const VType& s) {
    int n = s.size();
    vector<int> lps(n + 1);
    lps[0] = -1;
    int j = -1;
    for(int i = 0; i < n; i++) {
        while(j >= 0 && s[i] != s[j]) j = lps[j];
        j++;
        lps[i + 1] = j;
    }
    return lps;
}
Back to top page