(9)字符串（KMP and Hash）
字符串的KMP算法
经典问题：给出一个长度为n的字符串T，模板是一个长度为m的字符串P，求,问模板P在字符串T中的所有匹配点（假设T=“ABCABC”,P=“ABC”，匹配点有0,3）
解决：1、枚举每一个点的位置，暴力匹配，判断即可。时间复杂度为O（nm）；
2、运用字符串函数find直接查找
3、KMP算法：对模板串进行预处理出一个f数组，f[i]表示的是满足P[i-j...i-1]=P[0...j-1]的最大的j（j<i）,成为border。由于它充分利用了每一次匹配的信息，时间复杂度达到了O（n+m）。
举例来说，有一个长字符串"BBC ABCDAB ABCDABCDABDE"（即文本串），我想知道里面是否包含另一个模式字符串"ABCDABD"，它的位置在哪呢？
当空格与D不匹配时，你其实知道前面六个符"ABCDAB"已经匹配的部分。KMP算法的想法是，设法利用这个搜索词的子串（就是搜索词的某个前缀）的已知对称值，注意这里的对称非中心对称，而是基于搜索词的某一个前缀的对称信息，在不匹配的时候跳过一些不必要的位置来加速匹配速度，这样就提高了效率。
怎么做到这一点呢（如何跳过不必要的位置在不匹配时）？可以针对搜索词，算出一张模式字符串的前缀函数表。
已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查模式串的《前缀函数表》可知，其前缀（即ABCDAB）中的最后一个匹配字符B的位置对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数（直接将前面的对称信息调到后面的对称位置，跳过一些不必要的位置）：
移动位数 = 已匹配的字符数 - 当前已匹配字符串的部分匹配值
因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。
空格与A不匹配，继续后移一位。
逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位
读到这里你肯定觉得一脸懵逼。我们还有一个最重要的没讲，它就是————前缀函数表
前缀函数表
“前缀”与“后缀”的定义： "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
"前缀函数"的对称值（也叫部分匹配值）就是模式串的对应前缀中的"前缀"和"后缀"的最长的共有元素的长度（实质是最大对称程度）。以"ABCDABD"为例，
前缀函数表的意义
A,首先要搞清楚的是它是模式字符串的所有前缀产生的一张表，保存的值表征了最大对称度，我们一般用next数组来保存其某个前缀的对称值，例如next[6]=2，代表的就是模式串的某个有6个字符的前缀“ABCDAB”，这个前缀的对称度就是2，即“AB”是对称的。
B,模式串的某前缀的对称值的实质是，有时候，搜索词已经部分匹配了（一定是某个前缀），其某个前缀（已经匹配部分）的头部和尾部会有重复。比如，"ABCDAB"之中前缀有"AB"，后缀也有"AB"，那么它的"前缀函数对称值"就是2（"AB"的长度,且“AB”是"ABCDAB"所有前缀和后缀中的最长公有元素）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置，在这个新的位置我们跳过了不必要的比较位置，并且直接就有“AB”匹配。
前缀函数表的实现原理
BB了这么久，其中最重要的就是如何根据待匹配的模式字符串求出其所有前缀函数表中的最大对称值，在下文中我们将其存储在next数组中。
编程策略
1）、当前字符的前面所有字符的对称程度为0的时候，只要将当前字符与前面这个子串的第一个字符进行比较。这个很好理解啊，前面所有字符串的对称值都是0，说明都不对称了，如果多加了一个字符，要对称的话只能是当前字符和前面字符串的第一个字符对称。比如“ABCDA”这个里面"ABCD"的最大对称值是0，那么后面的A的对称程度只需要看它是不是等于前面字符串的第一个字符A相等，如果相等就增加1，如果不相等那就保持不变，显然还是为0。
2）、按照这个推理，我们就可以总结一个规律，不仅前面是0呀，如果前面字符串的的最大对称值是1（k），那么我们就把当前字符与前面字符串的第二（k）个字符即P[1]（P[k]）进行比较，因为前面的是1（k），说明前面的字符已经和第一（k）个字符相等了，如果这个又与第二（k+1）个相等了，说明对称程度就是2（k+1）了。有两（k+1）个字符对称了。比如上面“ABCDA”的最大对称值是1，说明它只和第一个A对称了，接着我们就把下一个字符“B”与P[1]（即第二个字符）比较，又相等，自然对称程度就累加了，就是2了。
但是如果不相等呢？那么这个对称值显然要减少，并且我们只能到前面去寻找对称值，而在找的过程我们同时也利用前缀函数表快速搜索找到与当前字符匹配的位置。比如假设是“（AGCTAGC）（AGCTAGC）T”（请无视字符串中的括号，只为方便看出对称），显然最后一个T的前一个位置的对称度是7,说明T的前一个位置的7个字符的后缀必与7个字符的前缀相等，然而T!=P[7]，说明T位置的对称度只能是比7小的长度的前缀，所以递减k值，递减为多少呢？当前字符前一个位置的对称度为k=next[13]=7，显然必须以7为基准减少，即在前缀长度为7以内的范围重新寻找以T结尾的前缀，所以k=next[6]，再接着判断是否相等,
3）、按照上面的推理，我们总是在找当前字符P[q]（q为遍历到的位置下标，见下面程序）通过其前一个位置的对称值判断是否与P[k]相等，如果相等，那么加，如果不相等，那么就减少k值，重新寻找与与P[q]相等的元素位置
核心代码
void MakeNext(const char P[],int next[]){
int k;//k:最大对称长度
int m = strlen(P);//模版字符串长度
next[0] = 0;//模版字符串的第一个字符的最大对称值必为0
for (int q = 1,k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值
{//在前一个位置的k不为0，但是却不相等，那么减少k，重新寻找与P[q]相等的位置，让下面的if来增加k
while(k > 0 && P[q] != P[k])//
k = next[k-1]; //while循环是整段代码的精髓所在，
if (P[q] == P[k])//如果相等，那么最大相同前后缀长度加1
k++;//增加k的唯一方式
next[q] = k;
}
} 代码解释（关于while）
已知前一个位置的最大相同前后缀长度为k，且k>0，即P[0]···P[k-1]； 此时比较第k项P[k]与P[q],如图1所示 如果P[K]等于P[q]，那么很简单跳出while循环; 如果不等呢？那么我们应该利用已经得到的next[0]···next[k-1]来求P[0]···P[k-1]这个前缀中最大相同前后缀。为什么要求P[0]···P[k-1]的最大相同前后缀呢？为什么呢？ 原因在于P[k]已经和P[q]失配了，而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同，看来P[0]···P[k-1]这么长的子串是用不了了，那么我要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]···Pj-1，看看它的下一项P[j]是否能和P[q]匹配。如图2所示
这个关于字符串匹配问题的KMP算法就这样讲完了。事后一句话：我去！我还是用find吧
字符串的Hash算法
经典问题：
【1】字符串的加密问题：对于一个长度为n的字符串。我们总希望它具有一个加密规则使同样的字符串加密所得结果必须相同，不同的字符串加密所得结果尽量不同。【2】判断两个字符串是否相同\查找长字符串中的模板字符串：用哈希函数算出对应字符串的哈希函数值，再运用直接对比\差分来判断两个字符串\子串之间的关系。
基本原理：
使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。
hash的优点
把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
hash的实现
首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：
得到key 通过hash函数得到hash值 得到桶号(一般都为hash值对桶数求模) 存放key和value在桶内。 其取值过程是:
得到key 通过hash函数得到hash值 得到桶号(一般都为hash值对桶数求模) 比较桶的内部元素是否与key相等，若都不相等，则没有找到。 取出相等的记录的value。 hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候).
由此可见，要实现哈希表, 和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。
int ELFhash(char*key)
{
unsigned long h=0;
while(*key)
{
h = (h << 4) + *key++;
unsigned long g = h & 0xF0000000L;
if(g)
h ^= g >> 24;
h &= ~g;
}
return h % MOD;
}