src/jiangly/string/02-Z-Func.hpp

• View this file on GitHub
• Last update: 2025-02-17 23:08:47+08:00
• Include: #include "src/jiangly/string/02-Z-Func.hpp"
• Link: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63378373
• Link: https://qoj.ac/submission/384405

Code

/**   Z函数
 *    2023-08-11: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63378373
 *    2024-04-09: https://qoj.ac/submission/384405 【模板】
**/
std::vector<int> Z(std::string s) {
    int n = s.size();
    std::vector<int> z(n + 1);
    z[0] = n;
    for (int i = 1, j = 1; i < n; i++) {
        z[i] = std::max(0, std::min(j + z[j] - i, z[i - j]));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] > j + z[j]) {
            j = i;
        }
    }
    return z;
}

#line 1 "src/jiangly/string/02-Z-Func.hpp"
/**   Z函数
 *    2023-08-11: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63378373
 *    2024-04-09: https://qoj.ac/submission/384405 【模板】
**/
std::vector<int> Z(std::string s) {
    int n = s.size();
    std::vector<int> z(n + 1);
    z[0] = n;
    for (int i = 1, j = 1; i < n; i++) {
        z[i] = std::max(0, std::min(j + z[j] - i, z[i - j]));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] > j + z[j]) {
            j = i;
        }
    }
    return z;
}

Back to top page