Manacher(马拉车)算法

发布于 2022-07-07  568 次阅读


string manacher(string s) {
    int l = s.length();
    if (l < 2) return s;
    //预处理字符串
    string t = "$";
    for (int i = 0; i < l; i++) {
        t += '#';
        t += s[i];
    }
    t += "#@";
    //计算数组p、起始索引、最长回文半径
    l = t.length();
    int mid = 0, maxx = 0;
    int maxLen = -1;
    int res = 0;
    for (int i = 1; i < l - 1; i++) {
        if (maxx > i)
            p[i] = min(p[2 * mid - i], maxx - i);
        else
            p[i] = 1;
        //向两边延伸,扩展右边界
        while (t[i + p[i]] == t[i - p[i]]) p[i]++;
        //更新右边界maxx和中心位置索引mid
        if (maxx < i + p[i]) {
            maxx = p[i] + i;
            mid = i;
        }
        //更新答案
        if (maxLen < p[i] - 1) {
            maxLen = p[i] - 1;
            res = i;
        }
    }
    int start = (res - maxLen) / 2;
    //截取字符串
    return s.substr(start, maxLen);
}

详解链接