提到字符串，就一定会提及响当当的KMP算法。KMP用于在字符串序列中检索子序列，是形式简单、内涵丰富的代表算法之一。
问题
如果对比两个序列，从头到尾逐元素对比就可以了。但是如果在一个长序列中检测一个短序列呢？
设长序列为S，短序列为s。
-
从S中找到s的第一个元素
-
从该元素起逐一比对，直至比对完成或遇见不匹配的字符为止
-
在S中重新寻找s的第一个元素，重复以上过程。
思考
上述做法中，只要比对失败，就重新来过，时间复杂度最高可以到O(M*N),其中N和M分别是长串和短串的长度。能否有改良的算法呢？
在比对的过程中，我们已经知道了短串的前几位是“ABCABD”，能否利用该有效信息呢？
KMP算法就是在这种情况下诞生的。
情况
我们假设有这样的情况：
s的后缀中前N个元素，可以与s的前N个元素重合。
例如：“ABD”是s的其中一个后缀，前两个元素AB与s的“ABCABD”中前两个元素AB重合。
这样的话，元素C和元素D就产生了一个联系。好比如说D的父母AB和C的父母AB是邻居，那么D和B一定是玩伴。
关联
已知i<j，A[i]前面一共有N个元素,这N个元素与A[j]前面的N个元素完全匹配，则称A[i]和A[j]是有关联的。
关联是一种期望的匹配关系。相关联的元素可以相等，可以不等。是否能匹配上，并不关心。
这种情况下，如果比对短串中的某个元素失败，不需要从头开始比对，只需要比对该元素的关联即可。
例如，S中的C与s中的D不匹配，只需要去匹配s中和D关联的C即可。如果匹配上，继续向后遍历。否则继续上述过程。
这样的话，如果匹配失败，只需要从关联位开始进行匹配，而非从子串头开始匹配。
关联数组
KMP算法核心是关联数组的求解。一个子串需要求出其对应的关联数组。
规则如下：
已知A[N-1]与A[M-1]相关联（N>M）,求A[N]的关联项。
- 如果A[N-1]与A[M-1]相等，则A[N]和A[M]相关联。
- 如果A[N-1]与A[M-1]不等，则向前寻找与A[M-1]相关联的项，尝试将A[N]与其建立关联关系，并重复以上规则，直至：
- 找到相等项：A[N]与该项后继建立关联
- 未找到相等项：A[N]与字符串首项建立关联
解释
- 如果A[N-1]与A[M-1]关联且相等，则他们的后继会产生关联。就如同父辈间的关系很好，则子女很大几率会联姻。
这种关联实际上就是期望的匹配关系，某个字符匹配上了，后继才能和下一个匹配。 - 如果A[N-1]与A[M-1]不等，则向前寻找与A[M]相关联的项，尝试将A[N]与其建立关联关系。简单说，x和y关联，y和z关联，则x和z关联。
上图中，z的前驱和y的前驱关联且相等，故z和y关联。但是z和y不相等，于是z去找y的关联项x，与它去匹配。如果还没匹配上，继续找x的关联项，直到匹配上或越界。
包办婚姻那些事
只有双方爸妈很熟的情况下，才会给双方的孩子订婚。例如y和z的爸妈很熟，于是y和z订了婚。后来两个年轻人性格不合分手，z很气愤地去和y的订婚对象x拍拖（请忽略性别关系），如果不成，继续找X的订婚者，直到找到一个性格相合的人结婚为止。如果最后都没有找到，暂时和字符串头订婚（表示单身）。
为什么关联有继承性呢？因为如果x和y有关联，说明x的前N项和y的前N项是重合的。也就是说，x和y关联，y和z关联，意味着它们前N项都一致，当然x和z可以关联。
如果z的爸妈和y的爸妈很熟，y的爸妈和z的爸妈很熟，则x的爸妈和z的爸妈通常很熟，x和z就可以订婚。
CODE1
void MakeNext(const char* s,int* next){
//0号字符不应与任何元素相关联，但是为了统一写法，与-1相关联
next[0]=-1;
for(int i=1;i<strlen(s);i++){
//i元素前驱
int fore=i-1;
//前驱的关联项
int j=next[fore];
//迭代关联项直至匹配完毕或越界
while(s[j]!=s[fore] && j >=0)
j=next[j];//递推计算
//如果最终可以匹配上
if(s[fore]==s[j])
next[i]=j+1;
//否则登记为单身
else
next[i]=0;
}
}
要点：
- 元素i的前驱fore的关联项是j，如果匹配不上，就匹配j的关联项next[j],next[next[j]]...直至j越界。
- 0号字符不应与任何元素相关联，但是为了统一写法，关联项是-1。因为匹配到头元素说明已经是最后人选了，再匹配下去当然是越界了。
- 需要保证next至少有n的容量
CODE2
int kmp(const char* S,const char* s){
int n=strlen(S),m=strlen(s);
int* next=new int[n];
MakeNext(s,next);
for(int i=0,j=0; i < n; ++i){
//如果不匹配就一直找关联项
while(j > 0 && s[j] != S[i])
j = next[j];
if (s[j] == S[i])
j++;
if (j == m){ //等于m而非m-1；因为上一个语句刚刚进行了j++。如果已经比对完最后一位，j++就是m
delete[] next;
return i-m+1;
}
}
delete[] next;
return -1;
}
网友评论