XCPC wiki - 字符串 05 - 回文串

Manacher Algorithm

Find the longest substring which is palindrome.

在搜索到$i$ 时，

• cc,ll,rr 已经找到的右边界最大的回文串的中心、左端和右端。
• p[i] 以$i$ 为中心的最长回文串长度。如果$i$ 在最长回文串之中，p[i] 至少是它对称位置的 p[mirror]。利用此性质快速计算 p[i]。

vector<int> manacher(const string& s) {
    string t = "#";
    for (auto c : s) t += c, t += '#';
    const int n = t.size();
    vector<int> r(n);  // 存储每个字符作为中心的最长回文子串的半径
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = min(r[2 * j - i], j + r[j] - i);  // 利用对称性初始化 r[i]
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i]++;  // 尝试扩展回文子串
        }
        if (i + r[i] > j + r[j]) {
            j = i;  // 更新最右边界和中心位置
        }
    }
    return r;
}

如果 rad[l + r] > r - l，表明子串$[\mathscr l,r)$ 是回文串。

CF1943B. Non-Palindromic Substring

定义一个字符串是$k$-good 的，当且仅当该字符串 存在 长为$k$ 的 非 回文子串。对于字符串$t$，定义$f(t)$ 为满足$t$ 是$k$-good 的正整数$k$ 的总和。对于给定的一个长为$n$ 的字符串$s$，你需要回答$q$ 个询问，每次询问给出$l,r$，求$f(s_ls_{l+1}\dots s_r)$ 的值。

数据范围：$1 \leqslant n,q \leqslant 2\cdot 10^5$。

存在转任意，考虑一个字符串是$k$-bad 的，则所有长为$k$ 的子串都是回文的。这个条件很苛刻，考虑到

$$s_{0}=s_{k-1}=s_{2}=s_{k+1}=\cdots$$

如果$k$ 为偶数，字符串是$k$-bad 的当且仅当它每个字符都相同，如果是奇数，要么每个字符都相同，要么是$ababa$ 的形式。

特判$k=|s|$，此时上述式子只有$s_{0}=s_{k-1}$ 成立，不能推出任何结论，因此只能$s$ 本身是回文的。

int n, q;
cin >> n >> q;

string s;
cin >> s;

vector<int> lst1(n), lst2(n);
for (int i = n - 1; i >= 0; i--) {
    lst1[i] = i + 1 < n && s[i] == s[i + 1] ? lst1[i + 1] : i + 1;
    lst2[i] = i + 2 < n && s[i] == s[i + 2] ? lst2[i + 2] : i + 2;
}

auto rad = manacher(s);
auto cal = [&](int l, int r, int d) {
    assert((r - l) % d == 0);
    return 1ll * (l + r) * ((r - l) / d + 1) / 2;
};

while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    int len = r - l;
    
    ll ans = cal(2, len, 1);
    if (lst1[l] >= r) {  // aaaa k= 偶数是 bad 的 
        ans -= cal(2, (len - 1) - (len - 1) % 2, 2);
    }
    if (lst2[l] >= r && lst2[l + 1] >= r) {   // abab k= 奇数是 bad 的
        ans -= cal(3, (len - 1) - len % 2, 2);
    }
    if (rad[l + r] > len) {   // [l,r) 是回文串 k=|s| 是 bad 的
        ans -= len;
    }
    cout << ans << "\n";
}  

回文自动机

struct PAM {
    static constexpr int ALPHABET_SIZE = 28;
    struct Node {
        int len;
        int link;
        int cnt;
        array<int, ALPHABET_SIZE> next;
        Node() : len{}, link{}, cnt{}, next{} {}
    };
    vector<Node> t;
    int suff;
    string s;
    PAM() {
        init();
    }
    void init() {
        t.assign(2, Node());
        t[0].len = -1;
        suff = 1;
        s.clear();
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
     
    bool add(char c, char offset = 'a') {
        int pos = s.size();
        s += c;
        int let = c - offset;
        int cur = suff, curlen = 0;
 
        while (true) {
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
                break;  
            cur = t[cur].link;
        }       
        if (t[cur].next[let]) {  
            suff = t[cur].next[let];
            return false;
        }
         
        int num = newNode();
        suff = num;
        t[num].len = t[cur].len + 2;
        t[cur].next[let] = num;
 
        if (t[num].len == 1) {
            t[num].link = 1;
            t[num].cnt = 1;
            return true;
        }
 
        while (true) {
            cur = t[cur].link;
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
                t[num].link = t[cur].next[let];
                break;
            }       
        }           
 
        t[num].cnt = 1 + t[t[num].link].cnt;
 
        return true;
    }
};