玉雕网站建设,美丽说网站建立的主要方式,山东省城市建设管理协会网站,常见的网络营销方式有哪几种字符串匹配的应用非常广泛#xff0c;例如在搜索引擎中#xff0c;我们通过键入一些关键字就可以得到相关的搜索结果#xff0c;搜索引擎在这个过程中就使用字符串匹配算法#xff0c;它通过在资源中匹配关键字#xff0c;最后给出符合条件的搜索结果。并且我们在使用计算…字符串匹配的应用非常广泛例如在搜索引擎中我们通过键入一些关键字就可以得到相关的搜索结果搜索引擎在这个过程中就使用字符串匹配算法它通过在资源中匹配关键字最后给出符合条件的搜索结果。并且我们在使用计算机时通常需要处理大量的字符串例如编写C语言时的标准输入和标准输出都是字符串的形式所以字符串匹配算法是一种非常重要的算法。
在介绍KMP算法之前先简要说明一下暴力匹配算法。暴力匹配算法的思路非常简单它通过将模式串与文本串中的子字符串以文本串的第一个、第二个...以此类推直到第N1-M个字符开始的长度为M的所有子串进行比较最后得到第一次匹配的位置。对于一个长度为N的文本串和长度为M的模式串暴力匹配算法的时间复杂度为.而KMP算法将时间复杂度减少到了。
KMP算法是由D.EKnuth、J.H.Morris和V.R.Pratt提出的时间复杂度为的字符串匹配算法。KMP算法之所以能将时间复杂度减少到这个量级是因为在KMP算法中充分利用了已匹配成功的部分使得文本串中的指针不需要像暴力匹配算法一样回溯到正在比较子串的开头第二个字符因为如果匹配失败指针会移动到匹配失败子串的第一个字符的下一个字符并重新开始比较在比较过程中文本串的指针一直在向后移动我们只需要回溯模式串的指针即可。
下面本文将用例子来详细说明KMP算法的思路及过程假设我们要在文本串acacfacace中找到模式串acace字符串末尾的\0字符省略。
在开始之前首先介绍两个概念前缀和后缀。字符串的前缀是指不包括字符串最后一个字符的所有子串对上述例子a,ac,aca,acac...acacfacac是文本串的所有前缀后缀就是不包括第一个字符的从后往前的串e,ce,ace...cacfacace是文本串的所有后缀。
acacfacace
acace
我们先开始从头匹配匹配成功的部分标为红色如上图。显然模式串的最后一个字符与文本串的下一个字符不匹配那么对于暴力匹配算法接下来就会将文本串的指针回溯到第一个c字符模式串的指针回溯到第一个字符。下面列出暴力匹配的一些步骤用绿色表示接下来要匹配的串注意标记的不是匹配成功的串用紫色标记上一次匹配失败的位置
acacfacace
acace 那么可以看到在f之前cac与aca仍然不匹配继续下一步
acacfacace
acace
在这一步中可以看到两个ac匹配成功了。那么我们仔细观察就会发现在第一步中已经匹配成功了acac子串对于下面两步的暴力匹配算法我们仍然需要拿出第一步中已经匹配成功的文本串的子串的一部分来与模式串进行比较。
显然文本串中已经匹配成功的算法一定是模式串的子串。那么我们就会发现上面两步暴力匹配算法就是多余的因为我们不需要比较文本串和模式串我们只需要考察模式串就会发现cac与aca是不匹配的也就是说这一步的暴力匹配算法可以删除。
下面我们进一步观察已经匹配的模式串和接下来暴力匹配的部分有什么关系。在上面的例子中如果我们将已匹配部分看成一个字符串那么cac和aca就是它的一个后缀和前缀ac和ac也是它的一个前缀和后缀也就是说在暴力匹配算法中的文本串指针还没有移出刚才比较成功的字符串时文本串和模式串的每次比较实际上都是已匹配部分的前缀和后缀的比较。所以当我们找到模式串中已匹配部分的最长相等前后缀那么将模式串的指针移动到这个前缀的下一个字符文本串的指针不用移动就可以继续比较因为我们知道模式串指针之前的部分一定是匹配的并且这个匹配部分一定是最长的。
我们需要建立一个next数组用来表示当模式串中一个位置的元素匹配失败时模式串的指针应该回溯到什么地方重新比较。这个回溯位置取决于匹配失败元素之前的子串的最长相等前后缀。比如在上面的例子中acac的最长相等前后缀的长度为2也就是说在下一次比较时模式串的长度为2的前缀已经匹配成功了所以只需要将指针移动到第三个字符即可。
KMP算法代码
int KMP(char* t, char* s) {//t为文本串,s为模式串int sl strlen(s);//模式串的长度int tl strlen(t);//文本串的长度int i, j;//next数组next数组标记每个模式串的字符匹配失败要返回的位置所以元素的个数与模式串长度相同int* next (int*)malloc(sizeof(int) * sl);if (next NULL) {perror(malloc);return -1;}//建立next数组j -1; i 0;next[0] -1;//如果不将next值设为-1那么第一个元素匹配失败时就会回到它自己这时候我们要将文本串的指针1//就需要单独的代码来完成这一部分将next设为-1就可以同时将两个指针都1这和匹配成功的逻辑是相同的while (i sl) {//i是快指针当它越界说明next建立结束//这里的代码逻辑是建立next数组的过程实际上是模式串的子串中的前后缀匹配过程//i始终指向已处理的子串的最后一个元素从i1开始如果i和j指向的元素相同那么这两个元素刚好是//i2元素的前缀和后缀所以当i2匹配失败时将指针移动到j1因为0和1位置的元素已经匹配//可以看到i和j始终是同时向后移动的也就是说它们始终走过相同的距离举一个特殊例子来说明这个next建立的原理//如果从j0i1位置开始i和j指向的元素始终相等那么当i指向最后一个元素时j指向倒数第二个元素//这时从第一个字符到j-1从第二个字符到i-1它们分别是已匹配子串的最长相等前缀和后缀那么当i匹配失败时//显然指针需要移动到j重新比较这个特殊的例子就说明了i指向位置之前的子串的某个后缀始终是与0到j的前缀相等的//并且是最长的因为只有满足一定的条件i和j才会同时1if (j -1 || s[i] s[j]) {//将j的初始值设为-1是为了处理当始终不满足后面的条件时将next的值设为0i;j;next[i] j;}else {j next[j];//当i和j位置的元素匹配失败时由于i之前的元素都已经建立了next值所以j进行回溯重新开始匹配}}//优化next数组//如果模式串中某个元素的next值指向的元素与它相同那么这个元素匹配失败时实际上不需要比较next值指向的元素//我们可以对next数组进行优化来避免这种情况//next[0]依然等于-1for (int i 1; i sl; i) {if (s[i] s[next[i]]) {//如果s[i]和该元素的next值指向的元素相同//那么将该元素的next值设置为其next值指向元素的next值由于是从前往后处理的所以新的next值指向的元素一定不等于它本身next[i] next[next[i]];}}//KMP算法过程i 0; j 0;while (i tl j sl) {if (j -1 || t[i] s[j]) {//如果需要从模式串的头开始匹配或者对应元素匹配成功i;j;}else {j next[j];//否则回溯j}}if (j sl) {return i - j;}return -1;
}
