迷茫的开发
分类： C/C++
2017-09-09 05:17:50
在实际编程中，会大量的使用字符串的匹配——或者是二进制的匹配。比如现在做的某项目，首先就是做的的查找。这是最优的算法吗？
这就是最常用的，也称暴力求解——就是用模式串依次去与主串比较，成功就返回。这个算法太简单就不在说了，主要看一下kmp。
kmp主要思想是在匹配失败时，将失败的信息利用起来。
举个极端的例子：模式串为，如果在x处不匹配，那么就没有必要匹配主串中
所以，模式串中没有重复的字符，可以在O(n)完成。
那对于通用的字符串匹配方法呢？再来看一下一个通用的例子，模式串P在q+1处与T不匹配了：
|
index |
|
|
|
|
s |
|
|
|
s+q |
|
|
|
|
|
|
|
|
|
T |
b |
a |
c |
b |
a |
b |
a |
b |
a |
a |
b |
c |
b |
a |
b |
|
|
|
|
s |
q |
|
|
|
|
|
|
|
||||||||
|
P |
|
|
|
|
a |
b |
a |
b |
a |
c |
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
s+q 已经遍历过了，用遍历过的匹配信息，来移动最大的距离？ |
|||||||||||||||||
|
P |
|
|
|
|
|
|
a |
b |
a |
b |
a |
c |
a |
|
|
|
|
|
|
s1 = s + 2 |
k |
|
|
|
|
|
|
|
||||||||
本来是S++，继续比较。但是可以从两个方面来去掉一定不会匹配的情况：（下面的描述T、P都只匹配的那一部分也就是分别只代表对应的阴影部分）
从前向后看：P希望尽可能向后移，比如图中P至少能移动两格——由上一轮可知T+1和b匹配，可能就不和a匹配。进一步，则需要在T中找出P的前缀。
从后像前看：前面匹配的再多也没有用，只要和T最后一个字符不匹配也不行。故从P中找出的子串，必须要是T的后缀。
所以下一次要比较的，就是从P中找出一个前缀，它又刚好是T的后缀。当然这要求该字符串是最长的。如下，选出aba
P的前缀：a,ab,aba,abab
T的后缀：a,ba,aba,baba
提示：1。既然T和P匹配，那么它们就相等，所以其实就是找的模式串中未匹配的前N个字符的字符串。那么解决的关键问题就是：求一个字符串中的最长子串s，它既是该字符串的前缀，又是该字符串的后缀。由于s为前缀，只需要一个下标就可以表示，这就是next数组的值。
2．当字符串匹配失效时，找到一个匹配的字符串，这是决定回溯的长度——因为我们得到的是不匹配的长度。如果没有没有找到这样的字符串，则直接跳过没有匹配的长度（的例子）
3．注意要找到最长的，这保证的是正确性。比如上列中有a,aba都可以选择，但是我们不确定T中最后的aba后面是否和P后面的匹配。
下一步我们来计算next数组，本人认为这才是难点，曾经看代码完全没有看懂。而自己实现，时间复杂度又没有保证。
通过上面的讲解可知: 模式串p 的next[k]表示：模式串P的前k个字符串组成的子串s满足上文提到的条件的子串长度。。
|
|
s |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
k |
|
|
|
|
k |
|
|
||||||||
|
P |
|
|
|
|
|
|
. |
. |
. |
|
|
|
|
|
|
|
|
|
0 |
|
next[k] |
|
|
k |
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|||||||||||
如果还是以暴力求解的观点来想：对于一个字符串Pat，求所有前缀（next的长度）的前缀与匹配的后缀最大长度。这就包含了pat长度、对每个前缀计算其前缀和后缀，这就达到了O（n??3)的时间复杂度！
下面我们来根据这个思路进行优化：
在遍历字符串Pat时，0到迭代器位置（i）表示了其前缀（O（N）），遍历的同时使用另外一个迭代器（j）表示该前缀的前缀。
这样，i也是next数组的下标，而j也就是next[i]的值，并且是pat[0…i]的前缀长度和后缀长度。
先看实现：
void get_next(const char* pat, unsigned long n, vector& next)
{
int i = 0, j = -1;
next[0] = -1;
while (i < n)
{
if (j == -1 || pat[i] == pat[j])
{
i++, j++;
if (pat[i] == pat[j])
{
next[i] = next[j];
}
else
{
next[i] = j;
}
}
else
{
j = next[j];
}
}
}
该源码中，else的部分是以前多次看KMP都始终不明白的地方，因此先说else部分：
对于else中的证明：
先抽象命题：对于s[0…i-1], s[0…j-1]满足条件，此时若s[i]!=s[j],那么至少s[0…next[j]]是满足条件的!（当然，也可以从0开始去遍历，此时会大大增加复杂度：不仅要回溯j,还要回溯i）
事实上，它又是反过来利用我们在kmp中求next的思想——充分利用比较过的信息，我们利用上图来证明
s[0…k],s[0…i]满足条件，我们有如下信息：
1.对于子串s[i], s[0…k]==s[i-k…i]， ——已知性质作用于i
2.对于子串s[0..k],s[0…next[k]] == s[k-next[k] ——已知性质作用于next[k]
由1、2可知s[i-next[k]]==s[0…next[k]] —— 等式的传递性
而next[k]的最大性可有上面的数学归纳法证明。
提示：证明说起来可能比较复杂，但是看上面那个表格就很清晰的：要证明的就是两处黄色前的两个表格相等！有了此结论，可以保持i不动，直接回溯了j，从而时间复杂度达到了O(n).
源码中条件成立时明显就是一个递推式——可用数学归纳法证明：
递推证明：
对于字符串S[0…n], 假设s[0…j]是s[i…j]
附加条件s[j+1]==s[i+1],那么s[0…i+1]
如果条件不成立，那么存在k>j,st s[0…k]满足条件，那么s[0…j]不满足条件，从而s[0…i+1]满足条件。
初值：
当i=0时，j=0;
其实暴力求解的方法，在实际应用中，通常不会保持较坏的性能，因为目标串和模式串很相似的情况很少。
比如相似的情况：
目标串：aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
模式串：aaaaaaaaaaab
从算法可以看出，其实只要模式串开头的部分和目标串不要太相似就在大多数情况下可以避免。但是采用KMP可以避免这种可能带来的抖动。
并且，算法和具体的产品应用不通，如果这里已经是比较关键的部分，提升2倍的性能也是可以优化的，而不是像算法那样认为是一样的！
