2019.3.3高中部集训

知识清单

  • $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

    3. $Code$实现生成$KMP$数组:

    1
    2
    3
    4
    5
    6
    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$匹配:
    1
    2
    3
    4
    5
    6
    7
    8
    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字符串匹配

    • 标程:
    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
    #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+ $注释

    1. 初始化:
    1
    2
    3
    4
    struct node{
    int son[MAXS];//子节点的分支个数
    int size,end;//所在的字符串个数,是字符串末尾的个数
    }Trie[MAXN];
    1. 插入:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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;
    }
    1. 查询:一个字符串$S$是否是给定字符串集合中某个前缀
    1
    2
    3
    4
    5
    6
    7
    8
    9
    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$

    • 分析:普通的字符串储存和前缀匹配,直接使用$Trie$字典树来做。
    • 标程:
    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    #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$自动机

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×