字符串全家桶

abv3Rpkg · 2025-01-04 17:08:06 · 个人记录

AC 自动机

解决多串匹配问题。具体地，所有查询串构成一棵 Trie 树，对于每一个节点维护 fail 指针，指向这个节点最长的在Trie树中出现的真后缀。

暴力的构建方式是简单的。设 u 通过字符 c 指向 p（t(u,c)=p），现要得出 fail(p)。若 t(fail(u),c) 存在，fail(p) 设为 t(fail(u),c)。否则查看 t(fail(fail(u)),c)，t(fail(fail(fail(u))),c)，直到找到一个存在的，或全部不存在，设为根节点。

但是这样看起来复杂度就不对。而且匹配也很难。考虑魔改 Trie 树成为字典图：将一条 t(u,c) 定义为在状态 u 后添加一字符 c 后在原 Trie 树上到达的状态。

建字典图和 Fail 指针可以揉在一起做：若 t(u,c) 在 Trie 上存在，则 t(u,c) 照样连。否则 t(u,c)\leftarrow t(fail(u),c)。无论如何 fail(t(u,c))\leftarrow t(fail(u),c)。bfs 维护即可。

fail 指针显然同样构成一棵树，一个节点通过 fail 的到根链即为其所有重要的后缀。而通过 Trie 的到根链是前缀，所以一个节点通过走这两棵树可以到达的节点就是其所有重要的子串。

SA

绷，半年前学的东西现在忘得一干二净了。

记 sa_i 表示字符串 S 中排名为 i 的后缀是哪个（记录其起始位置），rk_i 表示后缀 S[i,n] 的排名。核心思路是，如果我们有 S 所有长度为 w 的子串的大小顺序，通过一次双关键字排序即可得到所有长度为 2w 的子串大小顺序。操作直到 w>=n 即可。这里双关键字的值域是 n 所以可以用计数排序削掉一个 \log。

下面逐行分析代码在干什么。（字符串以下标1开头）

int sa[N],rk[2*N],tmp[N],buc[N];
void Sort(int n,int w){
    int ptr=0;
    for(int i=n;i>n-w;i--) tmp[++ptr]=i;
    for(int i=1;i<=n;i++) if(sa[i]-w>0) tmp[++ptr]=sa[i]-w;
    for(int i=1;i<=n;i++) buc[i]=0;
    for(int i=1;i<=n;i++) buc[rk[i]]++;
    for(int i=1;i<=n;i++) buc[i]+=buc[i-1];
    for(int i=n;i>=1;i--) sa[buc[rk[tmp[i]]]--]=tmp[i];
}
void SA(string s){
    int n=s.length()-1;
    for(int i=1;i<=n;i++) buc[s[i]]++,tmp[s[i]]=1;
    for(int i=1;i<=256;i++) buc[i]+=buc[i-1],tmp[i]+=tmp[i-1];
    for(int i=n;i>=1;i--) sa[buc[s[i]]--]=i,rk[i]=tmp[s[i]];
    for(int w=1;w<=n;w*=2){
        Sort(n,w);
        int ptr=0;
        for(int i=1;i<=n;i++){
            if(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+w]!=rk[sa[i-1]+w]) ptr++;
            tmp[sa[i]]=ptr;
        }
        for(int i=1;i<=n;i++) rk[i]=tmp[i];
        if(ptr==n) break;
    }
}

注：在代码中，对于在当前长度下相等的子串，其 rk[i] 相等（即 rk[i] 是在去重意义下的），但 sa[i] 直接代表某个有序排列，两两不等。对于两个相等的子串，其 sa[] 的大小关系没有保证。

SA() 的初始化部分：获得长度为 1 意义下的 sa[] 和 rk[]。
第二行 buc[s[i]]++,tmp[s[i]]=1;：buc[c] 记录 s[i]==c 的个数，tmp[c] 记录存不存在 s[i]==c。
第三行 buc[i]+=buc[i-1],tmp[i]+=tmp[i-1];：做前缀和，此时 buc[c] 记录 s[i]<=c 的数量，可以理解为所有 s[i]==c 的 i 在排列中构成一个“块”，buc[c] 是这个块的末尾。 tmp[c] 记录 c 的去重排名。
第四行 sa[buc[s[i]]--]=i,rk[i]=tmp[s[i]];：前半句找到 s[i] 所在的块，将 s[i] 放在这个块的末尾，然后将末尾前移，使同一块内的元素从后往前填满整个块。后半句就是记录 s[i] 的排名。

Sort(n,w)：当前的 sa[] 和 rk[] 均是在长度为 w 意义下，将 sa[] 更新到 2w 意义下，没管 rk[]。
Sort 中，tmp[] 存储子串的临时顺序，和 sa[] 类似。第一轮中，tmp[] 存储 i 按照第二关键字 rk[i+w] 的顺序。
第二行 将 i+w>n 的 i 放在最开头。它们的 rk[i+w]=0。
第三行 if(sa[i]-w>0) tmp[++ptr]=sa[i]-w;：升序遍历 rk[i+w]，挨个放入 tmp[] 中。升序的方式是依据 rk[sa[i]] 对于 i 升序。我们需要加入的第二关键字是 rk[w+1] ~ rk[n]，我们只要这部分。
第五行 buc[rk[i]]++; 同 SA() 第三行，维护“块”的末尾，只不过关键字变成了 rk。
第六行倒序处理 sa[buc[rk[tmp[i]]]--]=tmp[i];：按照第二关键字（tmp[]）降序的顺序，找到每个元素对应的“块”，从后往前填充。“块”的顺序保证第一关键字升序，遍历顺序保证块内第二关键字升序。

SA() 的倍增部分：根据 sa[] 更新出 rk[]，临时放在 tmp[] 里。tmp[sa[i]] 应该是单调不降，相等当且仅当 sa[i-1] 和 sa[i] 的两个关键字都相等。这是简单的。
优化 if(ptr==n) break; 第一关键字互不相同，后面的没必要做了。