src/jiangly/string/01A-Manacher.hpp

• View this file on GitHub
• Last update: 2025-02-17 23:08:47+08:00
• Include: #include "src/jiangly/string/01A-Manacher.hpp"
• Link: https://qoj.ac/submission/380047
• Link: https://qoj.ac/submission/384389

Code

/**   马拉车（Manacher 旧版）
 *    2024-04-06: https://qoj.ac/submission/380047
 *    2024-04-09: https://qoj.ac/submission/384389 【模板】
**/
std::vector<int> manacher(std::string s) {
    std::string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    std::vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = std::min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

#line 1 "src/jiangly/string/01A-Manacher.hpp"
/**   马拉车（Manacher 旧版）
 *    2024-04-06: https://qoj.ac/submission/380047
 *    2024-04-09: https://qoj.ac/submission/384389 【模板】
**/
std::vector<int> manacher(std::string s) {
    std::string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    std::vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = std::min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

Back to top page