src/jiangly/string/10-KMP.hpp

• View this file on GitHub
• Last update: 2025-02-17 23:08:47+08:00
• Include: #include "src/jiangly/string/10-KMP.hpp"
• Link: https://qoj.ac/submission/253754
• Link: https://qoj.ac/submission/384408

Code

/**   前缀函数（KMP）
 *    2023-11-17: https://qoj.ac/submission/253754
 *    2024-04-09: https://qoj.ac/submission/384408 【模板】
**/
std::vector<int> kmp(std::string s) {
    int n = s.size();
    std::vector<int> f(n + 1);
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) {
            j = f[j];
        }
        j += (s[i] == s[j]);
        f[i + 1] = j;
    }
    return f;
}

#line 1 "src/jiangly/string/10-KMP.hpp"
/**   前缀函数（KMP）
 *    2023-11-17: https://qoj.ac/submission/253754
 *    2024-04-09: https://qoj.ac/submission/384408 【模板】
**/
std::vector<int> kmp(std::string s) {
    int n = s.size();
    std::vector<int> f(n + 1);
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) {
            j = f[j];
        }
        j += (s[i] == s[j]);
        f[i + 1] = j;
    }
    return f;
}

Back to top page