【整理】算法竞赛字符科技学习笔记

KMP

KMP 是一种用于两个字符串匹配的算法。其核心概念是 Border ,即一个字符串同长度的完全相同的前后缀(通常不含自身)。

KMP 的做法是先求出要匹配的字符串(短串)的所有前缀的最长 Border,然后在于长串进行匹配,并在无法匹配时跳转到其 Border 进行再次尝试匹配。详细方法可以参考我之前的学习笔记

有时也会用 $next_i$ 表示字符串 $S$ 的前缀 $Preffix_i$ 的非平凡的最大 Border。

时间复杂度为 $O(n)$。

Hash

字符串 Hash 就是指将一个字符串映射成一个整数值的方法,通常用来快速比较两个字符串是否相等。

多项式取模 Hash(模哈) 时一个常用的哈希方法,即将字符串转换为 26 进制(或其他进制)数后进行取模,为了减少哈希冲突的可能性,双模是一个更优秀的选择。

双模(多模):进行多次不同质数的单模哈希,有效降低冲突概率。在不泄露模数的前提下,没有已知方法可以构造冲突。

Trie 树

Trie 是一棵有根树,每个点至多有 $|\Sigma|$ 个后继边(即字符的可能种类数),每条边上有一个字符。每个点表示一个前缀:从跟到这个点的边上的字符顺次连接形成的字符串。
每个点还有一个终止标记:是否这个点代表的字符串是一个字典串(可以用 $match$ 数组将字典串映射到字典树上)。详细方法可以参考我之前的学习笔记

时间复杂度为 $O(n)$。

Border 树

对于一个字符串 $S,n = |S|$,它的 Border 树(也叫 next 树)共有 $n + 1$个节点:$0, 1, 2, \dots, n$。
$0$ 是这棵有向树的根。对于其他每个点 $1 ≤ i ≤ n$,父节点为 $next[i]$。

$next[i]$ 表示字符串 $S$ 的前缀 $Preffix[i]$ 的非平凡的最大 Border。

image-20240624141510116

上图就是一颗 Border 树(图源:牛客竞赛)

关键性质:

  • 每个前缀 $Prefix[i]$ 的所有 Border:节点 $i$ 到根的链。
  • 哪些前缀有长度为 $x$ 的 Border:$x$ 的子树。
  • 求两个前缀的公共 Border 等价于求 LCA。

例题:

AC 自动机(ACAM)

AC 自动机是 Trie 和 KMP 的结合,其构建分为以下两步:

  1. 构建 Trie 树。
  2. 构建 Fail 指针(失配指针)。

失配(Fail)指针: 对于 Trie 中的每一个节点(即某个字典串的前缀),它与 Trie 中所有串的最大 Border 即为失配指针。(这里的 Border 指的是广义 Border)

广义 Border:对于串 $S$ 和一个字典 $D$,相等的 $p$ 长度的 $S$ 的后缀,和任意一个字典串 $T$ 的前缀称为一个 Border。

如何进行查询?也分为两步:

  1. 在 Trie 树上依次遍历整个文本串(通过构建 Fail 指针时构建的通道在树上跳转),并给遍历的点都打上标记(加上权值,表示遍历了以该点为结尾的字符串)
  2. 对于通过 Fail 指针构成的图进行拓扑排序,把对应点的贡献也算入到 Fail 指针指向的点。

详细方法可以参考我之前的学习笔记

时间复杂度为 $O(n)$。

Manacher

Manacher 可以求出一个字符串中以每个点为中心的最大回文串长度。

Manacher 算法的步骤如下:

  1. 记录最右回文串的中心 $mid$ 和左右端点 $L,R$(最右回文串:所有已求得的回文串中,右端点最靠右的一个)。
  2. 假设我们已经求出了 $1,2,\dots,i-1$ 位置的 $Len$(即以该位置为中心的最长回文串长度),则对于 $Len[i]$:
    1. 若 $i > R$:暴力拓展,并更新最右回文串。
    2. 若 $i \le R$:找到 $i$ 关于 $mid$ 的对称位置 $j=2\times mid -i$。
      1. 若 $j − Len[j] + 1 > L$,即 $Len[j]$ 没有超过当前最右回文串的表示范围,直接令 $Len[i]=Len[j]$ 即可。
      2. 否则,令 $Len[i]=Len[j]$,然后再暴力拓展,并更新最右回文串。

PAM(回文自动机)

PAM 是一种能够识别所有回文子串的数据结构。

关键概念:

  • 节点:每个节点代表了一种回文串。结点的 $len$ 属性即为其对应的回文串长度。
  • 后继边:用 $trans(u, ch) = v$ 表示 $u$ 节点有后继边 $ch$ 指向 $v$ 节点。则有 $S(v) = chS(u)ch$,以及
    $len[v] = len[u] + 2$.
  • 失配边:每个节点都有一个失配边,用 $fail[u] = v$ 表示 $u$ 节点的失配边指向了 $v$ 节点。则有 $S(v)$ 是 $S(u)$ 的最大 $Border$,即最长回文后缀。

PAM 的构造方法的核心即为 $fail$ 的构造方法。我们通过枚举前一个位置的 $fail$ 并依次跳转 $fail$,判断是否合法来进行构造,其部分代码如下:

int get_fail(int v,int p){
    while(p-tr[v].len-1<0||s[p-tr[v].len-1]!=s[p]){
        v=tr[v].fail;
    }
    return v;
}

注意,PAM 有两个根结点,一个为奇长度根节点,长度为 $-1$,一个为偶长度根节点,长度为 $0$,且 $fail$ 互相指向。

在 insert 一个字符时,我们先找到父节点的 $fail$,然后将这个字符连接到该节点的后面。然后更新该结点的 $fail$ 为其父节点的 $fail$ 结点与该字符继续进行 $get_fail$ 的操作。

SAM(后缀自动机)

后缀自动机是一种自动机。SAM 上的某个结点都表示若干个子串,这些子串的特点是他们在原字符串上所有出现位置的右端点都相同。

对于每一个结点(状态)有三种属性,$to[u][ch]$ 表示状态 $u$ 添加上 $ch$ 字符所到达的状态;$fa[u]$ 或 $lnk[u]$ 表示 SAM 上树边的父亲节点,$l[u]$ 表示状态 $u$ 所能表示的最长子串的长度。

还有一些不会被记录的概念和性质:

  • $Right[u]$ 表示状态 $u$ 所表示的所有子串的出现位置的右端点集合。两个不同状态的 $Right$ 集合必然是不同的。
  • 任意串 $w$ 的后缀全部位于 $s(w)$(即 $w$ 对应的状态)的后缀链接路径上(即该点到根节点的路径上)。

SAM 的构建方法比较复杂,可以参考下述代码:

void add(int c){
    int p=last,np=++tot;//建新点 np
    // for(int i=0;i<26;i++) to[np][i]=0;
    l[np]=l[p]+1;last=np;cnt[np]=1;//更新相关属性
    while(p!=-1&&!to[p][c]){//从 p 点往上走到第一个 to[p][c] 不为空的点
        to[p][c]=np;//过程中所有点都向 np 连边
        p=fa[p];
    }
    if(p==-1) fa[np]=0;//如果一路到根,直接结束
    else{
        int q=to[p][c];//否则,考虑第一个已有的 q=to[p][c]
        if(l[q]==l[p]+1) fa[np]=q;//如果 l[q]==l[p]+1,直接链接父亲
        else{
            int nq=++tot;//否则,将 q 分为 nq 和 q 两个结点
            l[nq]=l[p]+1;
            for(int i=0;i<26;i++) to[nq][i]=to[q][i];
            fa[nq]=fa[q];fa[np]=fa[q]=nq;//更新相关属性
            while(p!=-1&&to[p][c]==q){//将 p 到根的路径上所有连向 q 的点都改为连向 nq
                to[p][c]=nq;
                p=fa[p];
            }
        }
    }
}

在构建完 SAM 后,很多题目需要在 Link 树上进行拓扑排序来更新答案,可以对所有状态根据 $l[s]$ 进行基数排序(桶排)来更新,代码如下:

vector<int> vec[N];
void topu(){
    for(int i=1;i<=tot;i++) vec[l[i]].pb(i);
    for(int i=s.length();i>=1;i--){
        for(auto u:vec[i]){
            cnt[fa[u]]+=cnt[u];
        }
    }
}

代码

KMP

void kmp(string a,string b){//a 为原串(长),b 为需要被匹配的串(短)
    int la=a.length(),lb=b.length();
    int j=0;
    for(int i=1;i<lb;i++){
        while(j&&b[i]!=b[j]) j=border[j];
        if(b[i]==b[j]) j++;
        border[i+1]=j; 
    }
    j=0;
    for(int i=0;i<la;i++){
        while(j&&b[j]!=a[i]) j=border[j];
        if(b[j]==a[i]) j++;
        if(j==lb){
            //printf("%d\n",i-lb+1); 这是 b 在 a 中出现的位置,从 0 开始
            j=border[j];
        }
    }
}

AC 自动机(ACAM,含 Trie)

struct ACAM{
    struct Trie_Tree{
        int fail,to[26],ans;
    }tr[N];
    int match[N],tot,in[N];
    inline void insert(string s,int k){
        int l=s.length();
        int u=0;
        for(int i=0;i<l;i++){
            if(!tr[u].to[s[i]-'a']){
                tr[u].to[s[i]-'a']=++tot;
            }
            u=tr[u].to[s[i]-'a'];
        }
        match[k]=u;
    }
    inline void Get_Fail(){
        queue<int> q;
        for(int i=0;i<26;i++)
            if(tr[0].to[i]) q.push(tr[0].to[i]);
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<26;i++){
                if(tr[u].to[i]){
                    tr[tr[u].to[i]].fail=tr[tr[u].fail].to[i];
                    in[tr[tr[u].to[i]].fail]++;
                    q.push(tr[u].to[i]);
                }
                else tr[u].to[i]=tr[tr[u].fail].to[i];
            }
        }
    }
    inline void query(string s){
        int l=s.length();
        int u=0;
        for(int i=0;i<l;i++){
            u=tr[u].to[s[i]-'a'];
            tr[u].ans++;
        }
    }
    inline void topu(){
        queue<int> q;
        for(int i=0;i<=tot;i++) if(in[i]==0) q.push(i);
        while(!q.empty()){
            int u=q.front();q.pop();
            in[tr[u].fail]--;
            tr[tr[u].fail].ans+=tr[u].ans;
            if(!in[tr[u].fail]) q.push(tr[u].fail);
        }
    }    
}AC;

Manacher

string init(string t){
    string tmp;
    tmp+="#";
    for(auto ch:t){
        tmp+=ch;
        tmp+="#";
    }
    return tmp;
}
int p[N];
void manachar(){
    int L=-1,R=-1,mid=-1;
    for(int i=0;i<s.length();i++){
        if(i>R){
            mid=i;R=i;L=i;
            while(R+1<s.length()&&L-1>=0&&s[R+1]==s[L-1]){
                R++;L--;
            }
            p[i]=R-mid+1;
        }
        else{
            int j=2*mid-i;
            if(j-p[j]+1>L){
                p[i]=p[j];
            }
            else{
                mid=i;L=2*i-R;
                while(R+1<s.length()&&L-1>=0&&s[R+1]==s[L-1]){
                    R++;L--;
                }
                p[i]=R-mid+1;
            }
        }
    }
}

PAM

string s;
struct PAM{
    int u=0,tot=1;
    struct node{
        int to[26],fail,cnt,len;
    }tr[N];
    void init(){
        tr[0].len=0;tr[1].len=-1;
        tr[0].fail=1;tr[1].fail=0;
    }
    int get_fail(int v,int p){
        while(p-tr[v].len-1<0||s[p-tr[v].len-1]!=s[p]){
            v=tr[v].fail;
        }
        return v;
    }
    void insert(char ch,int pos){
        u=get_fail(u,pos);
        if(!tr[u].to[ch-'a']){
            tr[++tot].fail=tr[get_fail(tr[u].fail,pos)].to[ch-'a'];
            tr[u].to[ch-'a']=tot;
            tr[tot].len=tr[u].len+2;
            tr[tot].cnt=tr[tr[tot].fail].cnt+1;
        }
        u=tr[u].to[ch-'a'];
    }
}PAM;

SAM

string s;
struct Suffix_Automaton{
    int to[N*2][26],fa[N*2],l[N*2];//fa 和 lnk 是一个东西
    int tot,last;
    int cnt[N*2];

    Suffix_Automaton(){
        fa[0]=-1;
    }
    void add(int c){
        int p=last,np=++tot;
        // for(int i=0;i<26;i++) to[np][i]=0;
        l[np]=l[p]+1;last=np;cnt[np]=1;
        while(p!=-1&&!to[p][c]){
            to[p][c]=np;
            p=fa[p];
        }
        if(p==-1) fa[np]=0;
        else{
            int q=to[p][c];
            if(l[q]==l[p]+1) fa[np]=q;
            else{
                int nq=++tot;
                l[nq]=l[p]+1;
                for(int i=0;i<26;i++) to[nq][i]=to[q][i];
                fa[nq]=fa[q];fa[np]=fa[q]=nq;
                while(p!=-1&&to[p][c]==q){
                    to[p][c]=nq;
                    p=fa[p];
                }
            }
        }
    }
    vector<int> vec[N];
    void topu(){
        for(int i=1;i<=tot;i++) vec[l[i]].pb(i);
        for(int i=s.length();i>=1;i--){
            for(auto u:vec[i]){
                cnt[fa[u]]+=cnt[u];
            }
        }
    }
}SAM;
本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇