说在前面：

自从被刘老师赶出来机房了，没有办法好好在OJ上刷题，于是就借着各种闲杂课看看各种知识点吧，题目等到暑假的时候一定要刷个够。昨天老师基本没有讲什么课，所以就用来学习算法了。

Trie树

Trie树定义：

Trie,又称单词查找树,是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。

Trie树构建：

Trie树拥有有3个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含1个字符,每个节点都有26个分叉。
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

下面是个trie树的例子：

这里运用了非常巧妙的方法因为可能会出现各种字符重复，所以说这样就可以非常棒的进行存储，通过解决各种重复性的问题从而节约空间和查询的时间（效率是和字符串的重复度有关的）

在这个Trie结构中，保存了t、to、te、tea、ten、i、in、inn这8个字符串，仅占用8个字节

Trie树的每个节点下面应该有26[‘a’..’z’]个分支。当然，如果要区分大小写，就要多开了！一般都用指针来写，不过我们可以开个足够大的静态数组也可以。
基本26叉的数组，1万的容量基本是1M的存储空间。
按照竞赛的数据规模，我们用60万的静态数组完全足够了。

Trie树代码：

存储结构体

1
2
3
4
5
6
struct node
{
    char ch;
    int endflag;
    int Link[26];
}tree[610000];

Trie树的建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void add(int k,int node)  //k是s的第k个字符，node为当前节点。
{
    int  chindex=s[k]-‘A’;  //字符的编号
    if (tree[node].link[chindex]==0)   //新开节点
	{
		tree[node].link[chindex]=++len;
		tree[len].ch=s[k];
		tree[len].endflag=false;
	}
	int nexnode=tree[node].link[chindex];  //下一个节点的下标
    if (k==(int)s.size()-1)
    {
        tree[nexnode].endflag=true;
        return;
    }
    add(k+1,nexnode);
}

Trie树的查询

1
2
3
4
5
6
7
8
9
10
11
bool find(int k, int last,int node)
//k是要查找字符串s的第k个元素
{
    int chindex=s[k]-'a';
    if (tree[node].link[chindex]==0)  return false;
    int nextnode=tree[node].link[chindex];
    if (k==(s.size()-1)) //如果k是最后一个字符
       if (tree[nextnode].endflag)  return true;
        else return false;
    return find(k+1,last,nextnode);
}

Aho-Corasick自动机

我们先来看一道题：

【P1366】给你N个单词(N <= 10000) ，再给一篇文章（文章长度len<=1000000 ）.
问有多少个单词在此文章中出现过。

【分析】基本的kmp 的时间复杂度是 N*len。KMP算法，它是用于单个串的线性匹配算法 .强大的p数组让KMP的匹配到了O(N)级别。
trie树在乎的是公共前缀。

那么，能不能在 trie树上做kmp呢？Kmp上的p数组很强大，我们肯定要在trie树上的每个节点构造出自己的p数组。一般的文章都是在trie树上开一个 fail域，有时候叫 fail指针，失败指针。

这就是AC自动机算法的核心思想。

AC自动机的原理：

Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。

AC自动机主要用于多关键字的字符串匹配。 要搞懂AC自动机，先得有模式树（字典树）Trie和KMP模式匹配算法的基础知识。

  • 如有模式串 { she, he, say, shr, her, ayd }
    要对串 yshersayd 进行匹配 。
    Kmp是对上面6个单词依次构造属于自己的P数组，依次枚举去验证。而AC自动机通过构造 失败指针 来 优化匹配，从而使算法复杂度达到 O(n)。

  • 失败指针是在所有模式串或其前缀中找一个最大的那个 K，即对于串 S1，我们在其它模式串或其前缀中找一个串 S2，使得S1[len(S1)- k, len(S1)]= S2[0, k] 其中 k 最大，则 S1[ len(S1) ] 的失败指针为 S2[ len(s2) ]。

  • 也可理解为当我们匹配失配时，利用已经匹配的结果，尽可能的将指针 i 往后移。

  • 如下图，当我们用 ‘shersayd’ 匹配时，匹配到 ‘e’ 时以后的字符失配，这时我们不是用 ‘hersayd’ 继续从头开始匹配。利用匹配的结果，我们可以只用 ‘sayd’ 在红圈的另外那个 ‘e’ 开始匹配。失败指针就是在匹配失败时转移，使得能够继续匹配。

  • 上图中，粗红线表示失败指针，没标明失败指针的结点的失败指针都指向根结点。构建了失败指针后，匹配是如果不能匹配就从失败指针走，再匹配。如我们匹配刚才 那个字符串 ’yshersayd’，首先是字母 ‘y’ ，没有匹配，走向失败指针根结点，然后字母 ‘s’，匹配，走 向 ‘s’。然后字母 ‘h’，匹配，走向 ‘h’。然后字母 ‘e’ 走向 ‘e’，得到模式串 ‘she’。然后 ‘r’ ，这时 ‘r’ 失配，我们走向 ‘e’ 的失配指针，粗红线指向的另一个 ‘e’，继续匹配，得到模式串 ‘her’。依次进行。可知，匹配过程就是在一个图中走动，图中某一个结点标记了匹配了某个模式串。

AC自动机的实现：

AC自动机的实现有如下几步：

  1. 定义trie树结构
  2. 构造trie树
  3. 计算每个节点的fail指针。
  4. Fail指针的构造就是在trie树上不停的往回找。其原理就是用bfs得到trie的层次图，(下面这句话是重点) 当前节点的子节点的fail指针等于当前节点的fail指针的子节点。
  5. 进行查询

【细节】如果用c++的string。用cena评测发现大数据 c++的string的时间是 c语言 char 数组的4倍。
仔细体会下面的代码，然后自己一口气敲出来，就可以提交了。

AC自动机用一句话来定义就是在trie树上做kmp，fail域就是 kmp的p数组。这个是需要我们深刻理解的。

AC自动机的代码：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
struct node
{
    int endflag; //是否是某个单词的最后一个字符.小心有多个重复的单词
    int fail;  //失败指针
    int link[26]; //26个分叉
} tree[510100];
char s[1001000];  //用字符数组代替字符串，在1000000 个字符条件下，速度会快一些。
//string s;
int n,m,len=0,ans,slen;
int head,tail,root=0;
int q[510000];
void add(int k,int node)  //k是s的第k个字符，root为当前节点。
{

    int chindex=s[k]-'a';
    if(tree[node].link[chindex]==0)   //新开节点
    {
        tree[node].link[chindex]=++len;
        tree[len].endflag=0; //因为存在有多个相同的单词
        tree[len].fail=root;
    }
    int nexnode=tree[node].link[chindex];
    if(k==slen-1)  //恰好是一个单词的结尾。
    {
        tree[nexnode].endflag++;
        return;
    }
    add(k+1,nexnode);
}
void init()
{
    scanf("%d\n",&n);
    memset(tree,0,sizeof(tree));
    for(int i=0;i<n;i++)
    {
        scanf("%s",s);
        slen=strlen(s);  //因为字符串比较多，用了c语言的字符串读入。
        add(0,root);
    }
}
void buildac()//生成fail指针，建好AC自动机
//用bfs生成一个层次序列，fail指针肯定往前跳。按层次依次求出fail指针
{
    head=tail=0;
    q[tail]=root;
    while (head<=tail) //bfs广度优先遍历 trie树
    {
        int now=q[head++];//  当前的节点
        int temp; //用来存储临时的fail指针，是tree的下标
        for(int i=0;i<26;i++)
        if(tree[now].link[i])  //求link[i].fail指针
        {
            int nextnode=tree[now].link[i];
            if(now!=root)//如果是根，那么fail肯定是root
            {
                temp=tree[now].fail;
                while(!tree[temp].link[i] && temp)//找不到与 link[i]匹配的前缀  且没有退到根
                temp=tree[temp].fail; //继续向上退
                tree[nextnode].fail=tree[temp].link[i];
            }
            q[++tail]=nextnode;  //让这个子节点进队。
        }
    }
}
void find()
{
    ans=0;
    int now=root;
    scanf("%s",s);
    len=strlen(s);  //这里用的也是c语言的字符。
    for(int i=0;i<len;i++)
    {
        int chindex=s[i]-'a';
        while( !tree[now].link[chindex] && now!=root)//如果找不到，往回返
        now=tree[now].fail;
        now=tree[now].link[chindex];//下一层传递。
        int temp=now;//如果找到某个单词
        while(temp!=root&& tree[temp].endflag>-1 ) //如果找到某个单词，累加到结果
        {
            ans+= tree[temp].endflag;
            tree[temp].endflag=-1;
            temp=tree[temp].fail;
        }
    }
    printf("%d",ans);
}
int main()
{
    init();
    buildac();
    find();
    return 0;
}