HDU3068 回文串 Manacher算法

2022-10-12 13:12:24

好久没有刷题了，虽然参加过ACM，但是始终没有融会贯通，没有学个彻底。我干啥都是半吊子，一瓶子不满半瓶子晃荡。
就连简单的Manacher算法我也没有刷过，常常为岁月蹉跎而感到后悔。

问题描述

给定一个字符串s，求最长回文子串。
回文子串的回文指的是abccba这种从前往后读和从后往前读一样。
子串必须连续（比如从i到j，s[i:j]），不是最长子序列（最长回文子序列怎么求？），子序列是可以不连续的。

算法大意

ans[i]表示以字符i为中心的最长回文子串的长度
now表示now+ans[now]取得最大值的那个下标
对于当前字符i，如果i处在以now为中心的回文子串里，那么ans[i]的求法可以参考i关于now的对称点的回文子串长度，也就是ans[now-(i-now)].
例如：1j34now67i9，假设ans[j]=1,那么ans[i]也等于1，因为i和j都处在以now为中心的回文子串里面，它们是对称的。

上面所述即为算法关键，其余情形很容易自己想到。
但是Manacher算法用到了两个技巧

加#号，统一处理

ans[i]中记录的是以i为中心的最长回文子串，如果不作处理，这样只能够检测出长度为奇数的回文子串的最大长度。所以有一个巧妙的预处理。
给定字符串abcc，扩充成#a#b#c#c#。
#a#b#a# 长度为3，以字符为中心的情况
#a#a#a#a# 长度为4，以#为中心的情况
这样奇数偶数统一化处理。

首部加上一个怪异字符$,减少条件判断

如果在for循环中检测两个条件，那是很费事的，效率低。
如何判断一个条件有很多次无效的判断？就看这个条件发挥作用，影响程序分支的次数和进行条件求值的次数。
边界条件判断影响分支的次数很少，但却每次都要进行判断。
通过加上一个终止字符，就能够避免边界条件判断。
在Manacher算法中，要求回文子串同时要防止下标越界。所以直接在开头插入一个\$字符，这样肯定因为失配而终止。

复杂度分析

Manacher算法为线性复杂度，因为从前往后有一个指针一直是单方向运动，没有回溯。
对于数组中的多个指针，如果都是单向运动，尽管它们运动的顺序和步长不同，那也一定是线性复杂度。

代码

#include<stdio.h>
#include<iostream>
using namespace std;
const int N = 110009;
char s[N];
char a[N * 2];
int ans[N * 2];
int now;
int main(){
    freopen("in.txt", "r", stdin);
    while (scanf("%s", s) != -1){
        if (s[0] == 0)continue;
        //#号法预处理
        int j = 0;
        a[j++] = '$';//这样就能少判断一点，不用考虑边界问题了
        for (int i = 0; s[i]; i++){
            a[j++] = '#';
            a[j++] = s[i];
        }
        a[j++] = '#';
        //开始算法主体部分
        now = 1;
        ans[0] = ans[1] = 0;
        for (int i = 2; i < j; i++){
            if (now + ans[now] < i){//如果当前字符不在阴影里，只能自力更生
                int k = i;
                while (a[k] == a[i - (k - i)]) k++;
                ans[i] = k - i - 1;
                now = i;
            }
            else{
                int right = now - (i - now);
                if (right - ans[right]>now - ans[now]){
                    ans[i] = ans[right];
                }
                else{
                    int k = now + ans[now];
                    while (a[k] == a[i - (k - i)])k++;
                    ans[i] = k - i - 1;
                    now = i;
                }
            }
        }
        //寻找答案，这部分可以直接放在求ans的过程中
        int ma = 0;
        for (int i = 1; i < j; i++){
            if (ma < ans[i])ma = ans[i];
        }
        printf("%d\n", ma);
    }
    return 0;
}

最长回文子序列

动态规划：复杂度都是O（n^2）
方法一：
a[i,j]表示s[i,j]之间最长回文子序列。则a[i,j]可以来自a[i+1,j-1],a[i-1,j],a[i,j-1].
方法二：
将s和s反过来得到的字符串求最长公共子序列

码农公寓