当前位置：首页 > news >正文

53网站客服系统哪个好中国免费域名注册平台

news 2025/7/19 18:10:22

53网站客服系统哪个好,中国免费域名注册平台,深圳宝安区疫情情况,magento怎么做b2b网站引言： 在计算机科学中，字符串匹配是一个常见的问题，即在一个主串中查找一个模式串是否出现。朴素的字符串匹配算法需要对主串和模式串进行逐个字符的比较，时间复杂度为O(m*n)，其中m和n分别是主串和模式串的长度。然而…

引言：

在计算机科学中，字符串匹配是一个常见的问题，即在一个主串中查找一个模式串是否出现。朴素的字符串匹配算法需要对主串和模式串进行逐个字符的比较，时间复杂度为O(m*n)，其中m和n分别是主串和模式串的长度。然而，当主串和模式串较长时，这种暴力匹配算法的效率较低。

为了提高字符串匹配的效率，KMP（Knuth-Morris-Pratt）算法应运而生。KMP算法通过构建一个next数组，利用模式串的局部匹配信息来实现快速的字符串匹配。相比于朴素的暴力匹配算法，KMP算法具有更高的效率，时间复杂度为O(m+n)。

本篇博客将介绍KMP算法的原理和实现方法。我们将详细解释next数组的求解过程，并给出具体的实现代码。同时，我们还将讨论KMP算法的应用领域和一些相关的扩展问题。

希望通过本篇博客的介绍，你能够深入理解KMP算法，并能够应用于实际问题中。让我们开始探索KMP算法的奥秘吧！

BF算法

是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T 的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和 T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。时间复杂度为O(m*n),一般不推荐使用。

假定我们给出字符串 ”ababcabcdabcde”作为主串，然后给出子串： ”abcd”,现在我们需要查找子串是否在主串中出现，出现返回主串中的第一个匹配的下标，失败返回-1 ;

只要在匹配的过程当中，匹配失败，那么：i回退到刚刚位置的下一个,j回退到0下标重新开始。

对应的代码模板如下：

/* str:主串 sub:子串 */
int BF(char *str,char *sub) { 
assert(str != NULL && sub != NULL); if(str == NULL || sub == NULL) { return -1;
}int i = 0; int j = 0; int strLen = strlen(str); int subLen = strlen(sub); while(i < strLen && j < subLen) { if(str[i] == sub[j]) {i++; j++; } else {//回退 i = i-j+1; j = 0; } 
}if(j >= subLen){return i-j;}return -1;
}

KMP算法

KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。

区别：KMP 和 BF 唯一不一样的地方在，我主串的 i 并不会回退，并且子串的 j 也不会移动到 0 号位置。

那么我的主串不回退，我要怎么进行移动子串上的j来进行匹配呢？

答案是移动j到当前字符串前缀和后缀相同的地方，这样就避免了重复匹配的多余操作，从而将O(m*n)的算法降为O(M+N)的算法。我们用next数组来记录每次不匹配时j应该跳到的位置k。

而 K 的值是这样求的：

1、规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1 下标

字符结尾。

2、不管什么数据 next[0] = -1;next[1] = 0;在这里，我们以下标来开始，而说到的第几个第几个是从 1 开始；

求next数组的练习：

练习 1：举例对于”ababcabcdabcde”，求其的 next 数组？

-1 0 0 1 2 0 1 2 0 0 1 2 0 0

练习 2：再对”abcabcabcabcdabcde”,求其的 next 数组？ "

-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0

接下来就是对于next[i+1]=?的求解从而得到一个普适公式：

我们先假设next[i]=k成立，那么p[0]…p[k-1]=p[x]…p[i-1]，因为前缀和后缀的长度相等，则x=i-k。那么当p[k]==p[i] 时，next[i+1]=k+1。

那么当p[k] != p[i] 时，那么k就要回退到next[k] 如果此时p[k]==p[i],那么next[i+1]=k+1,如果还是不等就要一直回退直到k=0,如果p[0]==p[i]，那么next[i+1]=1，如果还是不等，next[i+1]=-1+1=0。

那么接下来来看代码：

void GetNext(int *next,const char *sub){int lensub = strlen(sub);next[0] = -1;next[1] = 0;int i = 2;//下一项int k = 0;//前一项的Kwhile(i < lensub)//next数组还没有遍历完{if((k == -1) || sub[k] == sub[i-1])//{next[i] = k+1;i++;k++;//k = k+1???//下一个K的值新的K值}else{k = next[k];}}
}
int KMP(const char *s,const char *sub,int pos)
{int i = pos;int j = 0;int lens = strlen(s);int lensub = strlen(sub);int *next = (int *)malloc(lensub*sizeof(int));//和子串一样长assert(next != NULL);GetNext(next,sub);while(i < lens && j < lensub){if((j == -1) || (s[i] == sub[j])){i++;j++;}else{j = next[j];}}free(next);if(j >= lensub){return i-j;}else{return -1;}
}