字符串

Posted on 2020-11-04 Edited on 2026-03-02 In OI Word count in article: 936 Reading time ≈ 3 mins.

临门一脚之字符串复习

回文串

Manacher

就是处理回文串的一个玩意，时间复杂度空间复杂度均为 \(O(n)\)，挺有用的一种工具吧。

预处理

由于串的长度有奇数也有偶数就很烦，为了方便讨论，就会往字符串里插入一些字符变得规整一点。

如：\({abcba}\rightarrow{\#a\#b\#c\#b\#a\#}\)，\({abccba}\rightarrow{\#a\#b\#c\#c\#b\#a\#}\)

然后就把串强制变成了一个长度为奇数的串，所以转移的话就很方便，不需要考虑回文串的奇偶性。

转移

计 \(p_i\) 表示以字符 \(i\) 为回文中心的回文半径，然后就会发现一件很有趣的事情：现在的回文半径刚好就是原串的回文长度 \(+1\)。

那么现在这里提出一个十分暴力的做法，非常的显然：

1	while (str[i + p[i]] == str[i - p[i]]) ++p[i];

如果直接整样跑的话，它显然是一个 \(O(n^2)\) 的暴力。

所以考虑用已知状态转移过来，就是让每个点被扫过的次数为一个常数，来降低暴力的复杂度。

就是说，如果这个点在某个点的回文半径范围内，那么有些信息他是可以直接用的。

令 \(mx\)，为上一个回文中心的右端点，\(id\) 为上一个回文中心，有：

1 2	if(mx > i) p[i] = min(p[2 * id - i], p[id] - (i - id)); else p[i] = 1;

这个 p[2 * id - i] 表示的 \(i\) 关于 \(id\) 对称的那个点的回文半径，p[id] - (i - id) 则是这个点到当前中心的右边界的距离，取 \(\min\) 就是当前点的最小可行回文半径，正确性可以画图感性理解一下。

所以其实马拉车就结束了。。。

Code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e7 + 10;

int n, p[maxn], ans;
char s[maxn], str[maxn];

void init()
{
    str[0] = '#', str[1] = '#';
    for(int i = 0; i < n; i++) str[(i << 1) + 2] = s[i], str[(i << 1) + 3] = '#';
    n = (n << 1) + 2, str[n] = 0;
}

void manachar()
{
	init();
    int mx(0), id(0);
    for(int i = 1; i < n; i++) {
        if(mx > i) p[i] = min(p[2 * id - i], p[id] - (i - id));
        else p[i] = 1;
        for (; str[i + p[i]] == str[i - p[i]]; ++p[i]);
        if (p[i] + i > mx) mx = p[i] + i, id = i;
    }
}

int main(){
    scanf ("%s", s);
    n = strlen(s);
    manachar();
    for(int i = 0; i < n; i++) ans = max(ans, p[i]);
    printf ("%d\n", ans - 1);
}

回文自动机(\(\text{PAM}\))

也是处理回文串的一个玩意儿，时间复杂度是 \(O(n)\) 的，空间常数略大。

（图片来源：oi-wiki）

大概就长成这个样子，和 \(\text{Trie}\) 树类似的建图，然后通过构造失配指针来访问节点信息。

预处理

同样的，这个还是会出现回文串的长度为奇数和偶数的问题，所以就会出现两个根，分别表示奇根和偶根。

关于这个回文树，需要注意：

偶根的失配指针是奇根
奇根的长度默认为 \(-1\)

转移

找到了失配点，那么长度就可以直接 \(+2\) 了。

所以可以有如下构造失配指针的方法：

inline int GetFail(int X, int N)
{
    while (S[N - Len[X] - 1] !=  S[N]) X = Fail[X];
    return X;
}

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 2e6 + 10;
char S[Maxn];
int X, P, Q, Tot(1), Last, Lsa, Ans[Maxn];
int Ch[Maxn][30], Len[Maxn], Fail[Maxn];

inline int Newnode(int X)
{
    Len[++Tot] = X;
    return Tot;
}

inline int GetFail(int X, int N)
{
    while (S[N - Len[X] - 1] !=  S[N]) X = Fail[X];
    return X;
}

int main()
{
    scanf ("%s", S + 1);
    Fail[0] = 1, Len[1] = S[0] = -1;
    for (int i = 1; S[i]; ++i)
    {
        if (i > 1) S[i] = (S[i] - 97 + Lsa) % 26 + 97;
        X = S[i] - 'a';
        P = GetFail(Last, i);
        if (!Ch[P][X])
        {
            Q = Newnode(Len[P] + 2);
            Fail[Q] = Ch[GetFail(Fail[P], i)][X];
            Ans[Q] = Ans[Fail[Q]] + 1;
            Ch[P][X] = Q;
        }
        Last = Ch[P][X];
        Lsa = Ans[Last];
        printf ("%d ", Lsa);
    }
    system ("pause");
}