速通字符串

First Post:

Last Update:

Word Count:
4.1k

Read Time:
16 min

Page View: loading...

本文的全名为：《论如何速通 T 学过的所有字符串科技》

所以没学的这里就没有。

定义 （及其变形）为字符串，下标从 开始。

定义 为 的长度

定义 为 的 切片，。

定义前缀 为 （或者简写为 ），后缀 为 （或者简写为 ）。

定义 为两个串的最长公共前缀。

代码瞎写的，甚至没编译，当伪代码看就好，当然如果挂了可以修。

C/C++ 风格字符串操作

见 cppreference。

字符串哈希

PKUSC 不会字符串哈希挂了 50pts，自闭了。

考虑对于定义哈希为 ，然后显然如果 为质数的话则可差分，这样可以实现 的比较，并支持单点修改，并且还可以支持奇怪的东西比如表示两个字符串的差。

注意到 应当远大于哈希数量的平方以保证正确率，一般来说可以取 ，我觉得这年头 __int128 都放开了就没必要写双模哈希了，因为取两次模怎么想都比取一次模慢不少。

1
2
3
4
5
6
7
8
9
const ll mo=4500000000000000011,base=50000017;
struct num{
    ll a;
    num(const ll x=0){a=x;}
    operator ll()const{return(a);}
    num operator+(const num &b)const{return(a+b>=mo?a+b-mo:a+b);}
    num operator-(const num &b)const{return(a>=b?a-b:a-b+mo);}
    num operator*(const num &b)const{return((i128)a*b%mo);}
};

一个经典科技是二分加上哈希判断某两个字符串的 ，然后判断下一位就能得到它们的大小关系。

Trie

大概是大部分人学的第一个 DFA？

除了 ACAM 没甚么应用场合，感觉 01-Trie 用的比较多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct trie{
    int size;
    struct node{
        int s[26];
        bool leaf;
    }a[N<<4];
    char* add(char *s){
        int now=0;
        for(;32<*s;now=a[now].s[*s++-97])
            if(!a[now].s[*s-97])
                a[a[now].s[*s-97]=++size]={};
        a[now].leaf=1;
        return(s);
    }
    bool find(char *s){
        int now=0,re=0;
        for(;32<*s;)
            if(!(now=a[now].s[*s++-97])) return(0);
        return(a[now].leaf);
    }
};

Manacher

Manacher 比 KMP 简单所以先写 Manacher。

考虑求 中的回文，显然对于一个回文 ，前后删除相同数量的字符仍然是回文。所以所有回文的信息可以用中心点加上最长长度表示。

然后你发现对于一个字符串，将其反转得到的字符串里面的所有回文信息是不变的。

所以对于一个回文 ，其左半部分和右半部分的回文信息是完全一样的（反转的）。

那么，当我们求右半回文的时候，显然就可以直接复制左半部分的信息，注意不能超过大回文的最右端。

取右端点最右的一个作为大回文即可。

然后众所周知，回文的长度可以是偶数，所以我们在每两个字符中间随便塞个东西进去就可以全部转为奇数，最后连除二都不需要。

1
2
3
4
5
6
7
8
9
for(s[0]='@',s[1]='#';32<*InF;++InF){
    s[++n]=*InF;
    s[++n]='#';
}
for(int i=1,mid=0,r=0;i<n;++i){
    if(i<r) f[i]=min(f[(mid<<1)-i],r-i);
    for(;s[i-f[i]-1]==s[i+f[i]+1];++f[i]);
    if(i+f[i]>r) r=i+f[mid=i];
}

KMP

现在看来不如字符串哈希。

首先定义 border 为字符串中相同的真前缀与真后缀的字符串。

比如 bbabbabb 中 b,bb,bbabb 都是它的 border。

然后定义 表示 的最长 border 长度。

考虑求 ，对于 ，当 可以从 转移过来：

1
2
3
4
abaa
   abaa  pi[i-1]=4
abaab
   abaab pi[i]=5

当然可能条件并不满足，但你发现由于 ，所以在 后面加一个字符可以等价为在 后面加一个字符，所以你再试一下 能不能转移，然后你发现这个过程可以递归。

正确证明的话，考虑这样做肯定能得到一个 border，然后对于最长只需向前归纳最后把锅丢给空串即可。

1
2
3
4
for(int i=1;i<n;++i){
    for(int &j=p[i]=p[i-1];j&&s[j]!=s[i];j=p[j-1]);
    p[i]+=s[p[i]]==s[i];
}

或者你也可以将字符串定义到 上，然后定义空串的 为 ，这样就无需显式地判断边界。

1
2
3
p[0]=-1;
for(int i=2;i<=n;++p[i++])
    for(int &j=p[i]=p[i-1];~j&&s[j+1]!=s[i];j=p[j]);

然后考虑如何匹配，比如现在 已经匹配上了，如果 能继续匹配就继续匹配，如果不能匹配，那就选择 尝试匹配。

正确性考虑反证，如果按照这样得到的第一个匹配前存在一个没有被找到的匹配，显然这需要现在保留下来的 更长，因为留下来的必然是 border，所以这是与 的定义矛盾的。

1
2
3
4
for(int i=0,j=0;i<n;++i){
    for(;j&&s[j]!=S[i];j=p[j-1]);
    if((j+=s[j]==S[i])==n) printf("%d\n",i);
}

Z 函数

（Aka 拓展 KMP）

定义 ，否则 为 。

考虑 Manacher 类似的过程，对于 ，其会覆盖 向后的 个字符，那么对于后面的第 个字符，就有 ，也就是 的一段后缀会等于 的一段后缀，然后 是求过的，所以直接搬过来即可。

1
2
3
4
5
for(int i=1,l=0,r=0;i<n;++i){
    if(i<r) z[i]=min(z[i-l],r-i);
    for(;s[i+z[i]]==s[z[i]];++z[i]);
    if(i+z[i]>r) r=i+z[l=i];
}

这个东西的能力跟前缀函数有不少重叠，并且被 SA 完全包含，但是有时候可以让你不用写 SA，或者不用学习线性的 SA。

AC 自动机

（ACAM）

KMP 是自动机，Trie 也是自动机，所以可以拼起来得到一个新的自动机。

考虑对于若干模式串 对 进行匹配，我们将它们置入 Trie 中，同时处理出 中所有后缀的包含关系，

我们现在对目前匹配的 ，求出其最长的后缀满足 中存在一个 使得其前缀与该后缀相等，记录这个 的前缀在 Trie 中的位置。

那么对于下一个字符，如果 Trie 能接受就直接接受，不然就像 KMP 一样跳 border 就行，在 Trie 上定义 border 就是寻找任意一个位置使其 Trie 前缀等于当前后缀。

那么求这个 Trie 的前缀函数与 KMP 是一致的，对着父亲跳一下，没有继续跳，注意判断根的儿子不要连到自己了。

考虑时间复杂度，你能往前跳的次数最多为你能往后跳的次数，而后者显然是 。

然后你细细思考发现这个定义与网上大部分的实现写的东西是不一样的。

可以看看 ouuan 的博客的评论，实际上网上的定义就是你考虑我们将这个转移（DFA 上跳边称为转移）精细化一点，变成如果下一个字符是 的下一个结点。

首先原先 Trie 上的边是满足定义的我们不管它们，然后考虑对于不能接受的转移 ，那么是类似的，我们将它链接到所有 border 中最长的满足后继存在 转移的结点的 转移后的结点（或虚根）。

说白了就是，原先的过程是跳 border 找 ，如果没找到继续跳 border，跳到有 的位置，然后向 转移。现在直接处理出这个 的位置在哪里一次跳过去。

这样的好处是代码比较短，缺点是空间比较大（如果是对于转移边动态开点的话，但是 OI 范围内想必大家都是开满的，不过对于汉字这样字符集巨大的就需要讨论了）。

实际上 KMP 也能这么处理，我们称之为 KMP 自动机。

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
struct ACAM{
    struct{
        int s[26],fail,match;
        bool leaf;
    }a[M];
    int size,d[M];
    int add(char *s){
        int now=0;
        for(;*s>32;){
            int &nxt=a[now].s[*s++-97];
            now=nxt?nxt:nxt=++size;
        }
        a[now].leaf=1;
        return(now);
    }
    void build(){
        int h=0,t=-1;
        for(int *i=a[0].s,*r=i+26;i<r;++i)
            if(*i) d[++t]=*i;
        for(;h<=t;++h)
            for(int p=d[h],*i=a[p].s,*r=i+26,*f=a[a[p].fail].s;i<r;++i,++f)
                (*i?a[d[++t]=*i].fail:*i)=*f;
    }
    void match(char *s){
        for(int now=0;*s>32;++s)
            ++t.a[now=t.a[now].s[*s-97]].match;
    }
    void finish(){
        for(int t=size;t;--t)
            a[a[d[t]].fail].match+=a[d[t]].match;
    }
}t;

然后注意一下实现细节，首先我们使用队列因为要 BFS 整颗 Trie，然后对于根的儿子直接先加入进队列，因为它们无需构建也不能构建（全连到根节点）。

然后对于当前结点的 border 是保留了的，因为我们还需要跳 border 这样一个操作，不过就不需要显式地循环来找到转移 了，可以理解为这是一个序列自动机的前缀结构。

匹配需要注意因为字符串可以相互包含，非结尾的状态的前缀可能是结尾，所以若到了一个结点，则其所以 border 都被匹配了一次（尽管这些 border 可能不是一个 中的串），但是你并不能直接暴力跳 border 来解决问题，因为这样时间复杂度会起飞。

所以在匹配结束之后，我们倒序遍历整个 Trie 令每个结点将贡献打到 border 串上。

后缀数组

（SA）

重头戏。

首先后缀数组 定义为将所有后缀排序（显然因为长度不等没有相同）之后排名为 的后缀的起始位置（即 ）。

定义 为后缀 的排名。

考虑一个简单的方法，对于每个后缀将其长度补全至 ，使用基数排序从后往前排序，这样的时间复杂度是 。

然后我们仔细想想这就等同于在前面每次插入一个数进去，那为什么不归并呢？

所以我们从前往后倍增每次令每个后缀的长度都加倍，显然前后两部分都是排序好的，然后直接基数再排序一次即可。

考虑具体的实现，如果直接基数排序需要排序两遍，这样太慢了。

考虑这个过程是将第二部分排好序，然后将第一维放入桶中，然后按照第二部分倒序取出。

我们发现将第二部分排好序已经做了，所以不管。将第一维放入，考虑第三步。你发现第二部分最小的那些，是倍增之后后半部分全为空串的，然后是按照我们之前排序的顺序，可以直接遍历。

然后你发现每次倍增对于新生成的 都是直接覆盖的，所以我们可以开两个表示新的和旧的，每次用旧的生成新的，然后交换头指针即可。

这份代码里的字符串是定义在 的，用于减少边界的判断。

注意字符集应当从 开始定义，以便于同空字符区分。

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
void SA(){
    int *r0=_r[0],*r1=_r[1],*s0=_s[0],*s1=_s[1],m=27;
    // rk 临时数组 r0/r1；SA 临时数组 s0/s1；字符集 m
    
    // 放入桶中
    for(int i=1;i<=n;++i) ++c[r1[i]=s[i]-96];
    for(int i=1;i<m;++i) c[i+1]+=c[i];

    // 生成第一次的 sa 与 rk，如果两个后缀目前相同则具有相同的 rk
    for(int i=n;i;--i) s1[c[r1[i]]--]=i;

    for(int t=1;;t<<=1){
        // 交换头指针，清空桶
        swap(r0,r1);swap(s0,s1);
        memset(c+1,0,m<<2);

        // 放入桶中
        for(int i=1;i<=n;++i) ++c[r0[i]];
        for(int i=1;i<m;++i) c[i+1]+=c[i];

        // 从大到小遍历，如果其前面有一个串倍增过来就处理它
        // s0[i]-t 表示前面那个串
        for(int i=n;i;--i)
            if(s0[i]>t) s1[c[r0[s0[i]-t]]--]=s0[i]-t;

        // 这部分的倍增结果是空串，它们是最小的
        // 由于它们的 rk 已经互不相同，所以它们的遍历顺序是无关紧要的
        for(int i=n-t+1;i<=n;++i) s1[c[r0[i]]--]=i;

        // 生成 rk，对于目前相同的两个串生成相同的 rk
        for(int i=m=r1[s1[1]]=1,*sf=r0+t;++i<=n;)
            r1[s1[i]]=m+=r0[s1[i]]!=r0[s1[i-1]]||sf[s1[i]]!=sf[s1[i-1]];

        // 如果已经生成了 n 个互不相同的排名则直接退出
        if(m==n) break;
    }
    sa=s1;rk=r1;
}

然后对于后缀数组有一个很重要的应用，求任意两个后缀的 。

我们考虑对于排序后的数组，每个向前一个求 。

也就是定义 。

考虑如何快速求，因为两个原串相邻的后缀的差异较小的，可以考虑它们之间的情况。

例如对于后缀 ，即为 ，而 （以下设为 ）即为 ，将两个 中的后缀写出来，它们是：

假定我们已经知道后两者 （并且以下假定其大于 ），设其相等的部分等于 （ 某个字符），根据定义那么就有：

根据 的定义，后缀 小于后缀 ，也即后缀 小于后缀 ，并且因为它们的第一个字符相同，将其去掉并不影响大小关系，故有： 注意到 ，这样的话，后面就已经接近 了，考虑前面。

而又再次根据 的定义，我们知道后缀 是小于后缀 最大的后缀（即它不可能小于 ，否则与 的定义矛盾），那么必然有： 于是我们得到 必然是 的一个前缀，同时它也是 的一个前缀。

那么我们得到结论： （注意下标套的 不要忘了）

根据这个结论我们可以写出代码：

1
2
for(int i=1,j=0;i<=n;ht[rk[i++]]=j)
    for(j-=j&&1;s[i+j]==s[sa[rk[i]-1]+j];++j);

由于我们最多向前走 次，而向后走的步数为向前走的步数加 ，所以时间复杂度 。

等一下，所以求任意两个后缀的 在哪里？

我们考虑我们已经可以在排序好的数组上求相邻两个后缀的 ，那么两个不相邻的则是取中间的最小值，即：

（注意前面套的 ，以及后面具体的大小关系看清楚）

证明较为简单，考虑从前往后计算 ，如果变小了则说明此时存在字符 大于 的对应位置 ，若字符 重新等于 的对应位置，则说明其前面存在一个字符 大于 的对应位置。

所以任何缩短必然使得最终的长度小于等于这个数，所以上限就是这个 ，至于下限用等于的传递性即可证明。

回文自动机

（PAM aka EER Tree, Palindromic Tree）

回文自动机（或许应该叫回文树，但是我觉得 PAM 比较符合串串科技的感觉）可以高效地储存字符串中的回文信息。

首先我们要定义一个自动机，其结点储存 表示其表示的回文串长度、 表示儿子、 表示父亲。

具有两个虚结点，一个为奇根（），另一个为偶根（），偶根的 指向奇根。

然后定义除了根以外的结点的含义是，其表示的回文是其 指向的结点表示的回文、左右加上当前结点的字母的回文串，维护好 。

然后就没有了，定义给出了其构建，因为有 ，每次判断当前结点的左边跟新加的字符是否一样，一样就跳儿子，若不存在则新建节点，不一样就跳 。

时间复杂度证明跟 KMP 一样。

用途的话，比如说可以像 ACAM 一样倒着遍历打标记，即可统计任意回文的出现次数。

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
struct PAM{
    int size,len,last,in[N];
    bool vis[N];
    char *s;
    struct node{
        int cnt,s[26],len,fail,fa;
    }a[N];
    PAM(char *_s):s(_s){
        a[1].len=-1;
        size=a[0].fail=1;
        fa[len=0]=1;
        for(int n=strlen(s);len<n;++len){
            insert(s[len]);
            in[len]=last;
        }
    }
    int getfail(int x) {
        for(;len-a[x].len<0||s[len-a[x].len-1]!=s[len];x=a[x].fail);
        return(x);
    }
    void insert(char x){
        int now=getfail(last),c=x-97;
        if(!a[now].s[c]){
            a[++size].len=a[now].len+2;
            a[size].fail=a[getfail(a[now].fail)].s[c];
            fa[size]=a[size].fail;
            a[a[now].s[c]=size].fa=now;
        }
        ++a[last=a[now].s[c]].cnt;
    }
};
≡