Manacher Algorithm

Find the longest substring which is palindrome.

在搜索到ii 时，

  • cc,ll,rr 已经找到的右边界最大的回文串的中心、左端和右端。
  • p[i] 以ii 为中心的最长回文串长度。如果ii 在最长回文串之中，p[i] 至少是它对称位置的 p[mirror]。利用此性质快速计算 p[i]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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，表明子串[l,r)[\mathscr l,r) 是回文串。

CF1943B. Non-Palindromic Substring

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

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

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

s0=sk−1=s2=sk+1=⋯s_{0}=s_{k-1}=s_{2}=s_{k+1}=\cdots

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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";
}

回文自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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;
    }
};