next[i]: 部分匹配表的产生
-
部分匹配表的产生和前缀和后缀有关系
-
基本概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合； "后缀"指除了第一个字符以外，一个字符串的全部尾部组合
-
部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。 以"ABCDABD"为例：
A
AB
ABC
ABCD
ABCDA
ABCDAB
BCDABD
CDABD
DABD
ABD
BD
D
前缀：
A
AB
ABC
ABCD
ABCDA
ABCDAB
后缀：
BCDABD
CDABD
DABD
ABD
BD
D
ABCDABD: 每一个子串里面去找前缀和后缀中最长的相同的元素的长度 --- 部分匹配表
-
"A"的前缀和后缀都为空集，共有元素的长度为0；
-
"AB"的 前缀为[A]，后缀为[B]， 共有元素的长度为0；
-
"ABC"的 前缀为[A, AB]，后缀为[BC, C]， 共有元素的长度0；
-
"ABCD"的 前缀为[A, AB, ABC]，后缀为[BCD, CD, D]， 共有元素的长度为0；
-
"ABCDA"的 前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，共有元素的长度为1；
-
"ABCDAB"的 前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]， 共有元素为"AB"，共有元素的长度为2；(最长的相同元素长度)
-
"ABCDABD"的 前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]， 后缀为[BCDABD, CDABD, DABD, ABD, BD, D]， 共有元素的长度为0；
偶数的情况
-
把字符串对折，左右两边去找相同的字符串；如果有2个相同的字符串，共有元素的长度为2；
-
把字符串对折，如果左右两边没有相同的字符串，那前缀和后缀一定没有相同的字符串，共有元素的长度为0；
next 表
-
字符串ABCDA的部分匹配值：字符串ABCDA共有元素的长度(2) || 字符串ABCDA前缀和后缀相同的数目
-
三次不匹配的情况的移动位数--->原字符串的移动标准
-
移动位数 = 已匹配的字符数 - (当前字符串)对应的部分匹配值 ?? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 6? ? ? ? ? ? ? -???????? ? 2
-
移动位数 = 已匹配的字符数 - (当前字符串)对应的部分匹配值 ?? ???
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2? ? ? ? ? ? ? ?-? ? ? ? ? ?0
-
移动位数 = 已匹配的字符数 - (当前字符串)对应的部分匹配值 ?? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?6? ? ? ? ? ? ??-? ? ? ? ? ? 2
-
字符串已匹配的字符数是6，下一次匹配原字符串移动的位数是 6 - 2 == 4位，原字符串直接移到ABCD 从D的后面开始比较
-
部分匹配值用代码求解
匹配过程图解
-
原字符串为：pstr1->mem[ i ] ，给定字符串为：pstr2->mem[ j ] ，i = 0，j = 0，next[0] = -1
-
最开始的匹配：原字符串 pstr1->mem[0] 和给定字符串 pstr2->mem[0] 匹配失败，执行else语句 j = next[ j ]；?---> j = -1?--->下一次循环执行if语句(j == -1) ---> i++，j++ ---> i = 1，j = 0，pstr1->mem[1] 继续和 pstr2->mem[0] 匹配
-
pstr1->mem[1] 和 pstr2->mem[0] 匹配失败，执行else语句 j = next[ j ]；---> j = -1 --->下一次循环执行if语句(j == -1) ---> i++，j++---> i = 2，j = 0，pstr1->mem[2] 继续和 pstr2->mem[0] 匹配
-
pstr1->mem[2] 和 pstr2->mem[0] 匹配失败，pstr1->mem[3] 继续和 pstr2->mem[0] 匹配，匹配失败，pstr1->mem[4] 继续和 pstr2->mem[0] 匹配，直到pstr1->mem[4] 和 pstr2->mem[0] 匹配成功，pstr1->mem[5] 和 pstr2->mem[1] 匹配成功，pstr1->mem[6] 和 pstr2->mem[2]也匹配成功...
-
匹配到 pstr2->mem[6] 时，字符D匹配失败，pstr1->mem[10] !=?pstr2->mem[6]，pstr2->mem[6]对应的部分匹配值为2，下一步用 pstr2->mem[2] 处的字符C继续和pstr1->mem[10]匹配，相当于原字符串向右移动：j - next[ j ] = 6 - 2 =4 位
-
?向右移动4位后，pstr2->mem[2] 处的字符C再次匹配失败，由于字符C对应的next值为0，所以下一步用 pstr2->mem[0] 处的字符继续跟pstr1->mem[10] 匹配，相当于原字符串向右移动：j - next[ j ] = 2 - 0 = 2 位
-
移动两位之后，A 跟空格不匹配，原字符串后移1 位
-
pstr2->mem[6] 处的字符D再次匹配失败，因为pstr2->mem[6] 对应的next值,为2，下一步用pstr2->mem[2] 继续跟原字符串串匹配，相当于原字符串向右移动 j - next[j] = 6 - 2 = 4 位
-
匹配成功，过程结束
得到next 表
void getNext(LPSTR pstr, int next[])
{
int len = pstr->curSize;
int i = 0;
int j = -1;
next[0] = -1; //第0个位置的部分匹配表为-1
while (i < len) //i小于总长度
{
//通过j避免了-1下标
if (j == -1 || pstr->mem[i] == pstr->mem[j]) //j == -1 表示刚开始
{
i++;
j++;
next[i] = j; //记录部分匹配元素的长度
}
else
{
j = next[j]; //重置j为-1 还原成上一个部分匹配值
}
}
}?KMP算法实现?
-
得到部分匹配表的数后，只要改变移动位数即可
-
i 直接跳到了 next[j]??的位置比较了，而不是把 j 还原去比较- -->(移动位数的应用)，j不是像BF那样还原到开始位置
//两个串 next表
int KMP(LPSTR pstr1, LPSTR pstr2, int next[])
{
getNext(pstr2, next); //调用函数得到部分匹配表
//剩下操作和BF算法一样
int i = 0;
int j = 0; //通过下标判断的方式
while (i < pstr1->curSize && j < pstr2->curSize)
{
if (j == -1 || pstr1->mem[i] == pstr2->mem[j])
{
i++;
j++;
}
else
{
j = next[j]; //不相等按照部分匹配表去做移动
}
}
if (j == pstr2->curSize) //找到了
{
return i - j; //注意是最后一个元素的位置i-j才是要求的下标
}
return -1; //没找到
}测试代码??
数据结构 --- c语言实现串_考拉爱睡觉鸭~的博客-CSDN博客
LPSTR pstr1 = createstring("BBC ABCDAB ABCDABCDABDE");
LPSTR pstr2 = createstring("ABCDABD");
int next[8];
printf("pos:%d\n", KMP(pstr1, pstr2)); //打印对应下标的位置 15