2019.3.3高中部集训

浏览 1210 | 评论 0 | 字数 4746

Snowflake_Pink

2019年03月03日

知识清单

$KMP$
$Trie$字典树
$AC$自动机
哈希$（Hash）$

笔记

一、KMP

引入：众所周知，普通的字符串匹配非常慢（其实不慢，期望复杂度$O(n+m)$，但是非常容易卡成$O(nm)$。所以就发明了$KMP$，用3个作者的名字命名。
算法：我太懒了，不想写出$KMP$的模拟过程。$KMP$的精髓是：能在失配时直接跳到可能匹配的地方。
1. 要把失配数组$（KMP）$建立在匹配串意义下，而不是文本串。因为匹配串更加灵活。
2. 生成失配数组：匹配值是指前缀和后缀的最长共有元素长度（前缀指除了最后一个字符以外的全部头部组合，后缀指除了第一个字符以外的全部尾部组合）
匹配串为“ABCDABD”
1、“A"：
匹配值：0
前缀：NULL
后缀：NULL
2、“AB”：
匹配值：0
前缀：A
后缀：B
3、“ABC”：
匹配值：0
前缀：A、AB
后缀：BC、C
4、“ABCD”：
匹配值：0
前缀：A、AB、ABC
后缀：BCD、CD、D
5、“ABCDA”：
匹配值：1
前缀：[A]、AB、ABC、ABCD
后缀：BCDA、CDA、DA、[A]
6、“ABCDAB”：
匹配值：2
前缀：A、[AB]、ABC、ABCD、ABCDA
后缀：BCDAB、CDAB、DAB、[AB]、B
7、“ABCDABD”：
匹配值：0
前缀：A、AB、ABC、ABCD、ABCDA、ABCDAB
后缀：BCDABD、CDABD、DABD、ABD、BD、D
1. $Code$实现生成$KMP$数组：
```
int k=0;
for(int i=1;i<len2;i++){
    while(k && s2[i]!=s2[k])
        k=kmp[k];
    if(s2[i]==s2[k]) kmp[i+1]=++k;
}
```
1. 最后的字符串$KMP$匹配：
```
for(int i=0; i<len1; i++){
    while(k && s1[i]!=s2[k])
        k=kmp[k];
    if(s1[i]==s2[k])
        k++;
    if(k==len2)
        printf("%d\n",i-len2+2);
}
```

【洛谷】P3375 【模板】KMP字符串匹配

标程：

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int maxn=1000010;
char s1[maxn],s2[maxn];
int kmp[maxn];

int main() {
    scanf("%s",s1);
    scanf("%s",s2);
    int len1=strlen(s1);
    int len2=strlen(s2);
    int k=0;
    for(int i=1;i<len2;i++)
    {
        while(k && s2[i]!=s2[k])
            k=kmp[k];
        if(s2[i]==s2[k]) kmp[i+1]=++k;
    }
    k=0;
    for(int i=0; i<len1; i++){
        while(k && s1[i]!=s2[k])
            k=kmp[k];
        if(s1[i]==s2[k])
            k++;
        if(k==len2)
            printf("%d\n",i-len2+2);
    }
    for(int i=1; i<=len2; i++)printf("%d ",kmp[i]);
    return 0;
}

二、$Trie$字典树

引入：因为所有的树形结构都有一个基本特点：元素与元素之间的关系为继承的一对多的关系。所以$Trie$字典树可以很方便的储存和查找字符串。下面就是个字典树$\Downarrow \Downarrow$

算法：我太懒了，直接贴$Code+ $注释

初始化：

struct node{
    int son[MAXS];//子节点的分支个数
    int size,end;//所在的字符串个数，是字符串末尾的个数
}Trie[MAXN];

插入：

void insert(int t[],int l){//插入数组t[]，插入个数l
    int o=root;//当前结点，初始化为root根节点
    for (int i=1;i<=l;i++){
        Trie[o].size++;
        if (!Trie[o].son[t[i]])//需要的子节点没有就添加子节点
            Trie[o].son[t[i]]=++tot;
        o=Trie[o].son[t[i]];//更新当前节点
    }
    Trie[o].size++;//表面的意思
    Trie[o].end++;//表面的意思
    return;
}

查询：一个字符串$S$是否是给定字符串集合中某个前缀

bool query(int t[],int l){
    int o=root;
    for (int i=1;i<=l;i++){
        if (!Trie[o].son[t[i]])
            return false;
        o=Trie[o].son[t[i]];
    }
    return true;
}

例题：[【洛谷】$P2922$ [$USACO08DEC$]秘密消息$Secret$ $Message$](https://www.luogu.org/problemnew/show/P2922)

分析：普通的字符串储存和前缀匹配，直接使用$Trie$字典树来做。
标程：

#include <iostream>
#include <cstdio>

using namespace std;
struct node{
    int son[2];
    int size,end;
}Trie[500005];//题目中的数据范围好像标错了QAQ
int tot,root;
int m,n;
void insert(int t[],int l){
    int o=root;
    for (int i=1;i<=l;i++){
        Trie[o].size++;
        if (!Trie[o].son[t[i]])
            Trie[o].son[t[i]]=++tot;
        o=Trie[o].son[t[i]];
    }
    Trie[o].size++;
    Trie[o].end++;//不能直接=1，储存的是在这个字符结束的字符串个数
    return;
}
int query(int t[],int l){
    int o=root,ans=0;
    for (int i=1;i<=l;i++){
        ans+=Trie[o].end;
        if (!Trie[o].son[t[i]])
            return ans;
        o=Trie[o].son[t[i]];
    }
    return ans+Trie[o].size;//记得最后结点所在的字符串格式也要加上！
}
int main(){
    int len,t[10005]={};
    scanf("%d%d",&m,&n);
    for (int i=1;i<=m;i++){
        scanf("%d",&len);
        for (int j=1;j<=len;j++)
            scanf("%d",&t[j]);
        insert(t,len);
    }
    for (int i=1;i<=n;i++){
        scanf("%d",&len);
        for (int j=1;j<=len;j++){
            scanf ("%d",&t[j]);
        }
        printf("%d\n",query(t,len));
    }
    return 0;
}

三、$AC$自动机（依然因为太菜不会，暂时咕咕咕）

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/20/
最后修改时间：2020-04-13 11:12:58
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！

评论会由可爱的 AI 来审核鸭~

评论列表

暂无评论