威海外贸网站建设多少钱,简单的公司简介,建筑建设工程信息服务平台,html可以做网站分页KMP算法
KMP算法是一种改进的字符串匹配算法
Next[j] k :一个用来存放子串返回位置的数组#xff0c;回溯的位置用字母k来表示。其实就是从匹配失败位置#xff0c;找到他前面的字符串的最大前后相等子串长度。默认第一个k值为-1(Next[0] -1),第二个k值为0(Next[1] 0),我…KMP算法
KMP算法是一种改进的字符串匹配算法
Next[j] k :一个用来存放子串返回位置的数组回溯的位置用字母k来表示。其实就是从匹配失败位置找到他前面的字符串的最大前后相等子串长度。默认第一个k值为-1(Next[0] -1),第二个k值为0(Next[1] 0),我们只需要从第三个k值(Next[2])开始求next数组的长度与子串的长度相同 arr2[k] arr2[j] ⇒ Next [ j1 ] k 1 此时令j 5那已知信息就有 arr[j] ‘a’Next[j] k 2, arr[k] ‘c’,此时arr[j] ! arr[k] 那我们就让新的 k Next[ k ] 0一直都找不到那我们此时k肯定回溯到了数组头部即k - 1处那我们就停止回溯 Next [ j 1 ] k 1 ⇒ Next [ j 1] 0
#includestdio.h
#includestring.h//获得Next数组
void GetNext(int* Next, const char* arr2) //传入Next数组地址传入子串首地址
{//初始已知项 j 1int j 1;//i从2开始求 int i j 1;//此时k为0 int k 0; //子串长度int len2 strlen(arr2); //Next数组前两个默认值Next[0] -1; Next[1] 0;while (i len2) {if ((k -1) || arr2[k] arr2[i - 1]) {Next[i] k 1;k k 1; i; }else{k Next[k]; }}
}//KMP算法
int KMP(char* arr1, char* arr2)
{int i 0; int j 0; int len1 strlen(arr1);int len2 strlen(arr2);int* Next (int*)malloc(len2 * sizeof(int)); //为Next数组开辟一个与子串一样长的 //空间//借用Next函数得到Next数组的内容GetNext(Next, arr2); if (len1 0 len2 0 || len2 0) return 0;else if (len1 0 || len2 len1) return -1; //当arr1和arr2都没走到尽头 while (i len1 j len2) {if (arr1[i] arr2[j]){i;j;}else{//j回溯j Next[j]; }}//子串全部找到了if (j len2)return i - j; //开始匹配时的位置return -1; //否则就是主串走到尽头代表没找到
}int main()
{char arr1[] abababcabc; char arr2[] abcabc;char pos;pos KMP(arr1, arr2);printf(%d, pos);
}优化
先来看一个例子: 主串s“aaaaabaaaaac” 子串t“aaaaac”
这个例子中当‘b’与‘c’不匹配时应该‘b’与’c’前一位的‘a’比,这显然是不匹配的。c’前的’a’回溯后的字符依然是‘a’。
我们知道没有必要再将‘b’与‘a’比对了因为回溯后的字符和原字符是相同的原字符不匹配回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。我们改进后的next数组命名为nextval数组。
KMP算法的改进可以简述为 如果a位字符与它next值指向的b位字符相等则该a位的nextval就指向b位的nextval值如果不等则该a位的nextval值就是它自己a位的next值。
void GetNextval(SqString t,int nextval[])
//由模式串t求出nextval值
{int j0,k-1;nextval[0]-1;while (jt.length) {if (k-1 || t.data[j]t.data[k]) { j;k;if (t.data[j]!t.data[k]) nextval[j]k;else nextval[j]nextval[k];}else knextval[k]; }
}
