27、备战（一） 沈浩眯了眯 ...
-
“老师，我想吃黑米豆浆~”
“老师！快抱我去上厕所！要尿床了！”
“老师，老师~今天可不可以打一局游戏？就一局~”
“老师，分我条腿~我要翘着睡！”
“老师~零花钱，我要买糖吃！”
某只兔崽子无赖起来还真是让人哭笑不得，偏生孔万荣如今乐得迁就他，所以当沈浩终于可以再次竖着站在公寓里作妖的时候已经是8月16号，七夕的前一天。
“老师，你明天回去陪师母吗？”沈浩贼兮兮地看向了孔万荣。
孔万荣老脸一红，一筷子敲到了沈浩的手背上，“吃你的豆浆！有闲心去骗个小姑娘回来呀~”
“老师你说的哦~”沈浩典型的好了伤疤忘了疼，好不容易可以蹦两下了结果非要作死，“怡霖小妹妹倒是不错~”
不出所料，一筷子又敲到了沈浩的手背上，然后只听孔万荣嗔怒道：“信不信我把你吊起来揍一顿！”
沈浩吐了吐舌头，坏笑着看向了老师：“您舍不得的~”
孔万荣筷子一拍，明明被人戳穿了还可以理所当然地跟个大佬似的往靠背上一倒，“有劲儿了？去洗碗！”
沈浩撇了撇嘴，然后老老实实地收拾起碗筷，毕竟他现在能做的也只有这些小事了，也正因为他还可以为老师做些什么所以如今才能如此心安理得地和老师撒欢~
在教师公寓里呆的时间并不长，可沈浩一直很开心。
十分钟后，碗筷收拾完了，衣服也已经晾好。
沈浩打开笔记本，点进之前的那个平台——印象中这个点好像有一场全网公开赛，他还特地跟老师确认过的！
8月16日，九点整开始，限时三个小时。
沈浩看了看屏幕右下角：8:55，嗯，可以开始进场准备了。
撑着手向后抻了抻，闭着眼睛甩甩头，又拍了拍脸彻底醒醒神，然后在正好进入倒计时的那一刻点击“进入比赛”，十道题目的列表首页立马弹了出来。
这种题目不一定是由最简单的开始，也不一定难度的层次是递增或递减的，所以沈浩先把所有题目都看了一遍，心里对这些题有了一个大概的定位。
前三题倒是基础题，不过序号E和J那两道题倒是可能要花些时间想想。反正先从最简单的开始！
返回序号为A的题目界面，这是一道关键词搜索的题目，根据题目描述可知给定N个单词和一篇文章，求这篇文章中有多少个题中给出的单词。
如果暴力一点做，用每一个单词对字符串做KMP，这样虽然理论上可行，但是时间复杂度非常高！特别是当单词的个数比较多并且字符串很长的情况下就不能有效解决这个问题了，所以这时候就可以用到AC自动机算法。
P.S.其实上面那题就是典型的多模式串匹配问题，也就是AC自动机。下面可以简单介绍一下相关的内容，如果不感兴趣就直接跳过补充内容。
P.S.这里提到的KMP模式匹配算法是由三个人1977年联合发表的一个线性时间字符串匹配算法，为了纪念他们所以取了各自姓氏的第一个大写字母。具体的数学定义这里就不提了，简单来说就是“暴力”匹配，怎么个暴力法呢？就是两串字母（其实还可以是数字，标点，反正屏幕上所显示的都行），如果遇到一样的了就一起看下一个字母，如果不一样，第一串看的字母不变，第二串字母就再从第一个字母开始看【第二串字母这里就用到了“回溯”】，以此推类，直到第一串字母全部匹配完。
P.S.然而，上面讲的那叫“暴力匹配”算法，和KMP算法到底还是不同的。KMP算法在这里引入了一个next数组（数组，就是存了一堆数字的一个序列，然而其中不一定是数字，还可以是字符，这里强调的是序列，有序的排列。至于什么叫排列，我想想……集合应该知道吧？没错，就是存放相同属性的元素的一个容器，如果属性不同那就叫结构体。），这个算法的特色在于考虑到了两串字母（其实专业一点应该叫字符串）中万一有相同的部分呢？这时候第二串字符再回到第一个字母开始从头比较就有点浪费时间了，所以这时候可以把相同部分的那几个字母所在的位置记下来，一旦遇到相同的就可以直接去比较第二串字母中不同的那一部分。
P.S.终于把KMP算法简单介绍完了，然而，KMP只是在单模匹配下可以高效地完成工作，就是说给定一个字母和一串字母（或者是一篇文章里找一个单词）的情况下进行匹配用KMP算法是绰绰有余的，如果给的是很多个单词呢？每一个单词都用一次KMP算法吗？这将是多么庞大的工作量啊……
P.S.所以，沈浩同学在这里用的是AC自动机算法，AC自动机算法是基于字典树和 KMP算法的高级算法，以下补充内容将另作说明。
沈浩浅浅地勾了勾嘴角，数据结构他学得还好。
直接就点开了[提交]的窗口，选定[C++]，指尖快速地敲动键盘，大拇指时不时地轻轻点上空格，尾指扫过回车就是漂亮的一行。
不过十秒钟，光标已经移到了第六行：三行头文件调用库函数，一行基本的命名空间，一行常量定义，接下来要正式开工了！
首先，设定模式树，也就是字典树，用来存储所有需要匹配的N个单词。
P.S.这边的Trie树其实就是哈希树的变种，典型应用就是用于统计、排序和保存大量的字符串，当然，肯定不仅限于字符串~像搜索引擎系统就经常用它来进行文本词频统计。
不过，在建立字典树之前还要先定义每个单词的形式，也就是字典树上节点的结构体变量。
struct TrieNode
{
int count;
struct TrieNode *fail; //失配指针
struct TrieNode *next[MAX];//26个字母指针域
TrieNode()
{
count=0;
fail=NULL;
memset(next,NULL,sizeof(next));
}
};
很快地敲完了十几行，设定了一个fail指针，再指定26个字母指针域；判断当前节点是否是单词的结尾以及相应的个数。
然后建立字典树，创建插入单词的函数，设置节点的faiI指针为空，再求解每个节点的fail指针。
P.S.每个节点的fail指针指向的是以当前节点表示的字符为最后一个字符的最长当前字符串的后缀字符串的最后一个节点。也就是说，当给定的文章和Trie进行匹配时，如果与当前节点的关键字不能继续匹配，就应该去当前节点的fail指针所指向的节点继续进行匹配。
P.S.搜索字典项目的方法：
(1) 从根结点开始一次搜索;
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索;
(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
接下来基于队列（bfs）具体实现一下fail指针，然后构建AC自动机，再利用求得的fail指针进行匹配。
沈浩眯了眯眼睛，思路很清晰，手下没停，很快就敲完了两个函数。
最后再加一个主函数，沈浩轻飘飘地扫过了上面用到的几个函数，顺便检查了一下原则性的错误。
感觉状态还好，沈浩轻轻点击[提交]，然后目不转睛地等待着Judging变成Accept，“耶！”沈浩在心底偷乐了一下。
自动判定过后，界面跳转到了实时排名，不出所料，总罚时“0:4:12”沈浩暂居第一，看着A下面那一列罚时上咬着自己的那几个人，沈浩暗自加了一把劲。
P.S.总罚时：所有AC了的题的(耗时+错误次数*20min)的和。实时排名时，AC题数优先，题数相同时按罚时排序。有些比较正式的比赛设有封榜机制，即比赛最后一段时间内的提交结果将隐藏（除了自己都不可见），榜单也会停止更新，新的提交会显示为灰色，留作最后滚榜用。
偷瞄了一眼时间，这都过去十分钟了！沈浩赶紧点开了题目B，后缀数组，还是字符串匹配问题，题目大意是给一个数字k，再给一个字符串，需要求出有多少子串是恰好出现k次的。
这题的思路倒是不难，只要按照sa[ i]的顺序排列一下，然后框定一长度为k的区间，求height数组在这段区间的最小值，最小值一定是满足部分条件的，如果这个长度为k的区间上面的字符串或者下面的字符串有重复，那么需要减去他们之间的最大值。但是需要单独讨论一下k为1的情况。
P.S.解释几个数组的概念：
sa[i]表示字典序第i大的后缀下标(字典序排名依次是1len(string);
rank[i]表示下标为i的后缀字典序排名;
height[i]表示sa[i]和sa[i1]最长公共前缀的长度.
当然，如果后缀数组可以加上RMQ算法（区间最值查询）就更好啦！
……
一路过关斩将，沈浩一直是遥遥领先的，毕竟前面几题的最优算法都是他拿下的，直到第I题提交完之后他才发现排名表里突然冒出了一匹黑马！
作者有话说
第27章 备战（一）
