字符串总结（AC自动机）

1.字符串总结。 通过了这几天的字符串的学习，我所学习的字符串的内容大致有，前缀树， 哈希，kmp算法，ac自动机等内容。 Hash就是一个散列表，通过压缩映射存关键信息，需要掌握的就是处理字符串的算法以及处理冲突，在这当中，还要运用到前向星，以及数据结构的知识，在处理字符串时还要涉及一些数学方面的东西， Hash表建立的时间复杂度是O（n）， 而查找的时间复杂度是o（1）。我觉得Hash我用得并不是太顺手，我用的更多的是Trie前缀树。 Trie前缀树是一个保存字符串的集合，相比于hash表，它显得更好用并且更省空间，因为它是用前向星存储，通过树的dfs遍历来存储字符串，后面的ac自动机就是在trie树上面存的。Trie前缀树的建立运用了在学习数据结构时用指针建树的知识，用dfs建立一棵树，它的大致流程是： 1． 定义一个结构体，包含的成员有：一个大小为26的数组，一个count来记录每个节点连接到根节点的单词的个数，在对结构体定义一个根的指针。 2． 从根节点开始建立，如果该单词当前字母在树的当前层存在，就进入该节点，以此类推，如果该节点没有被访问过，那就建立一个节点，当到达该单词最后一个字母，在建立的节点的count值加一，这样做是因为，如果有一个单词与当前单词一样，那也能记录下来。这样就使后面的访问变得更加方便。 3． 在字典书中查找一某个单词为前缀的单词的个数那就简单多了， 只需要像建立trie树那样一个字母一个字母的找，只不过如果发现该字母在树中不存在，就要返回一个错误信息，而不是建立节点，如果把需要查找的单词的每一个字母都找完了，那就要返回count值，因为要考虑有两个单词相同的情况，count的作用就表现出来了。 总的来说，我觉得trie我掌握的还不错，相比于hash，我更喜好于用trie树。 KMP算法。在我的脑海中，KMP就是一直跳的算法，相比于老老实实的一个字母一个字母的匹配，它显得更胜一筹。对于小于26的字符，还看不出它的优点，而在大的字符串面前，他就优秀了，因为必然有多个字符相同（抽屉原理），所以它十分的省时间，在这当中，也用到了一些关于前缀的知识，通俗地讲，就是把从字符串第一位开始到后面某一位作为一个基准，这就引入了一个next数组，它记录了从当前位置到前面某个位置与前面提到的基准比较，匹配的位置，这个过程实现的难度也比较低，来看看大致流程： 1. 它分为两步，第一步就是建立next数组，这个有个关键，就是next数组的初始化，定义 next[0] = -1。第一步就是定义两个变量i，j，来模拟指针的作用，i初值为0，j初值为-1，以一个while语句作为大的循环，作用是让i指针只访问整个字符串，再循环内，如果i，与j所在的字母相等或者j在初始值，那么i++，j++，next[i] = j，否则就把j跳到next[j]; 2. 第二步就是匹配两个字符串，与第一步极为类似，就是第一步中的i指针指的是被匹配字符串并且i，j都要初始化为0，而这一步应该把i指向匹配的字符串，这一步还要加上一个if来判断j是否访问完了被匹配的字符串，如果是，那就打印或者返回，j就跳到next[j]；对于KMP算法有一些变式，如布条上最多能剪多少花，这样如果使用裸的KMP，那就包含了重复的部分，就要报错，就要在上面加黑字体那一步处做改动，j直接跳回-1； KMP算法的复杂度为o（m）预处理，o（n）匹配，所以加起来要o（m+n），KMP对1个匹配1个很有效，但是对多个就显得力不从心了，这时就要使用到AC自动机了。 AC自动机，刚学习ac自动机时，还真的以为能自动ac，ac自动机就是一种匹配多个字符串的高效的方法，如果要靠kmp来解决问题，那就要考k个n＋m，这个太浪费时间，写写暴力还行，不能拿全分，但是想一想，他浪费时间浪费在每个字符串都要单个的求next数组，单个的与文章匹配，我们想一想，如果我们把这些单个化为一个整体，那就节省时间了，把字符串结合在一起的方法有很多，比如什么hash，trie树，而ac自动机就是建立在trie树上面的，而原来KMP的next数组变成了树的fail指针，流程其实挺简单的，由于细节在trie树和kmp已分析过，所以大概分析一下，建树还是一如既往。要加一个set_fail函数来查找每个节点的fail，这个过程要说一下，就是fail一直跳，知道不为空的节点或根，在把fail指向节点或根，这样做原因是什么？想想并查集，它的一个优化就是直接接一根线到祖先（路径压缩），可能有异曲同工之妙啊，接了fail的先以后就要做做后一步了，把文章放到自动机上跑一边，就是和trie找前缀过程有点像，总之，ac自动机作用相当打，在kmp上更上一层楼。下面配上代码。