Manacher

BB

此时，一个数据结构菜鸡选手路过 QAQ

 

Introduction

Manacher算法，用于在O(n)时间内求解所有回文子串

 

Extend to Palindrome - UVA 11475

Description
在一个字符串尾部加入最少的字符，使其变为回文串
Sample Input

aaaa
abba
amanaplanacanal
xyz

Sample Output

aaaa
abba
amanaplanacanalpanama
xyzyx

Solution
如果用回文自动机的话，自然是后缀中的最长回文串+在此串中的前缀的翻转；
用Manacher也是一样的，直接判定满足i + d[i] - 1 = n的最小的i

#include <bits/stdc++.h>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<string, int> psi;
const int N = (int)1e5 + 15;
const ll inf = (ll)9e18;
const int MOD = 998244353;

char tmp[N], s[2 * N];
int d[2 * N];

inline void manacher(char* s, int n) {
    for(int i = 1, l = 0, r = -1; i <= n; i++) {
        int k = (i > r ? 1 : min(d[l + r - i], r - i + 1));
        while(i - k >= 1 && i + k <= n && s[i - k] == s[i + k]) {
            k++;
        }
        d[i] = k;
        if(i + k - 1 > r) {
            r = i + k - 1;
            l = i - k + 1;
        }
    }
}

int main() {
    while(~scanf("%s", tmp + 1)) {
        int n = 0, m = 0;
        s[++n] = '#';
        for(int i = 1; tmp[i]; i++) {
            s[++n] = tmp[i];
            s[++n] = '#';
            ++m;
        }
        manacher(s, n);

        int pos = n;
        for(int i = 1; i <= n; i++) {
            if(i + d[i] - 1 == n) {
                pos = i;
                break;
            }
        }

        int l = (pos - d[pos] + 2) / 2, r = (n - 1) / 2;
        //printf("? %d %d\n", l, r);
        if(l == 1 && r == m) {
            puts(tmp + 1);
        } else {
            printf("%s", tmp + 1);
            reverse(tmp + 1, tmp + l);
            printf("%.*s\n", l - 1, tmp + 1);
        }
    }
}

 

[国家集训队]最长双回文串 - Luogu P4555

Description
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。 输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（∣X∣,∣Y∣≥1|X|,|Y|≥1∣X∣,∣Y∣≥1）且X和Y都是回文串。
Sample Input

baacaabbacabb

Sample Output

12

Solution
用回文自动机的话，即维护每个位置的最长前缀回文和最长后缀回文，然后枚举取最大值；
用Manacher也是类似的，Manacher算法可以在O(n)时间内处理出每一个位置上的回文半径d[i]，记为二元组(i, d[i])。现在要维护每个位置上的最长前缀回文，考虑顺序枚举，则必然要取(i,d[i])中满足i最小且i + d[i] - 1 >= i的，而如果存在j < i且j + d[j] - 1 > i + d[i] - 1的，则这个i不会作为最优决策，因而可以发现i + d[i] - 1是非降的，因此可以考虑使用单调队列维护这一单调性，每次决策直接取队头，这样总复杂度是O(n)的。

#include <bits/stdc++.h>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<string, int> psi;
const int N = (int)2e5 + 15;
const ll inf = (ll)9e18;
const int MOD = 998244353;

template <typename T>
struct Deque {
    int head, tail;
    T que[N << 1];

    void clear() {
        head = tail = N;
    }
    void push_back(T x) {
        que[tail++] = x;
    }
    void push_front(T x) {
        que[--head] = x;
    }
    void pop_front() {
        head++;
    }
    void pop_back() {
        tail--;
    }
    T front() {
        return que[head];
    }
    T back() {
        return que[tail];
    }
    bool empty() {
        return head == tail;
    }
};
Deque<pii> dq;
int dp[2][N];
char tmp[N], s[N];
int d[N];
int sum[N];


inline void manacher(char* s, int n) {
    for(int i = 1, l = 0, r = -1; i <= n; i++) {
        int k = (i > r ? 1 : min(d[l + r - i], r - i + 1));
        while(i - k >= 1 && i + k <= n && s[i - k] == s[i + k]) {
            k++;
        }
        d[i] = k;
        if(i + k - 1 > r) {
            r = i + k - 1;
            l = i - k + 1;
        }
    }
}

int main() {
    while(~scanf("%s", tmp + 1)) {
        int n = 0, m = 1;
        s[++n] = '#';
        for(int i = 1; tmp[i]; i++) {
            s[++n] = tmp[i];
            sum[n] = i;
            s[++n] = '#';
            sum[n] = i;
            ++m;
        }
        s[n + 1] = 0;
        manacher(s, n);

        for(int k = 0; k < 2; k++) {
            dq.clear();
            for(int i = 1; i <= n; i++) {
                while(!dq.empty() && dq.front().second < i) {
                    dq.pop_front();
                }
                int nr = i + d[i] - 1;
                if(dq.empty() || nr > dq.back().second) {
                    dq.push_back(make_pair(i, nr));
                }
                dp[k][i] = sum[i] - sum[2 * dq.front().first - i - 1];
            }
            reverse(d + 1, d + 1 + n);
        }
        reverse(dp[1] + 1, dp[1] + 1 + n);

        int ans = 0;
        for(int i = 2; i + 2 <= n; i += 2) {
            ans = max(ans, dp[0][i] + dp[1][i + 2]);
        }
        printf("%d\n", ans);
    }
}