题目: 有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 请找到模
式串在主串中第一次出现的位置;
提示: 不需要考虑字符串大小写问题, 字符均为小写字母;
a b c a c a b d c
a b d
位置为：6
假设, 主串S = “abcababca” ; 模式串 T = “abcdex”
BF算法查找模拟:
主串：a b c a b a b c a
模式串：a b c d e x
KMP 模式匹配算法_next 数组值推导
我们把 T 串各个位置 j 值变化定义为一个 next 数组; 那么
next 的长度就是 T串的长度; 于是我们可以得出下面函数的
定义:
next[j] = 0 ,当 j = 1 时；
Max {k | 1<k<j , 且’p1…pk-1’ = ‘ pj-k+1 … pj-1’} 当此集合不为空时；
1，其他情况；
T = “abcabx”
读: • 当 j=1时, next[1] = 0
• 当 j=2时, j 由 1到 j-1 范围内只有字符 “a”, 属于其他情况 next[2] = 1;
• 当 j=3时, j 由 1到 j-1 范围内有字符 “ab”,显然 a 不等于 b, 属于其他情况 next[3] = 1;
• 当 j=4时, j 由 1到 j-1 范围内有字符”abc”,显然abc 不存在相等情况,则属于其他情况
next[4] = 1;
• 当 j=5时, j 由 1到 j-1 范围内有字符”abcd”,显然abcd 不存在相等情况,则属于其他情况
next[5] = 1;
• 当 j=6时, j 由 1到 j-1 范围内有字符”abcde”,显然abcde 不存在相等情况,则属于其他情
况next[6] = 1;
当 j=5时, j 由 1到 j-1 范围内有字符”abca”,显然 abca 前缀字符 “a” 与 后缀字符
“a” 相等 ; (由于 ’p1…pk-1’ = ‘ pj-k+1 … pj-1’,得到p1 = p4) 因此可以推算出 k 值为2; 因此
next[5] = 2;
• 当 j=6时, j 由 1到 j-1 范围内有字符”abcab”,显然 abcab 前缀字符 “ab” 与 后缀字符
“ab” 相等; (由于 ’p1…pk-1’ = ‘ pj-k+1 … pj-1’,得到 [p1, p3-1] = [p6-3+1,p5] ) 推导 k 值为 3,
因此next[6] = 3;
解读:
经验: 如果前后缀一个字符相等,K值是2; 两个字符相等是3; n个相等k值就是n+1;
j = 5的情况
主串S: abcad
模式串: abcab
j = 6的情况
主串S: abcabc
模式串: abcabx
T = “ababaaaba”
解读:
• 当 j=1时, next[1] = 0
• 当 j=2时, j 由 1到 j-1 范围内只有字符 “a”, 属于其他情况 next[2] = 1;
• 当 j=3时, j 由 1到 j-1 范围内有字符 “ab”,显然 a 不等于 b, 属于其他情况 next[3] = 1;
• 当 j=4时, j 由 1到 j-1 范围内有字符 ”aba”, 显然”aba”, 前缀字符 “a” 与 后缀字符 ”a”
相等,所以 k = 2; next[4] = 2;
• 当 j=5时, j 由 1到 j-1 范围内有字符 ”abab”, 显然”abab”, 前缀字符 “ab” 与 后缀字
符 ”ab” 相等,所以 k = 3; next[5] = 3;
j = 4的情况
主串S: abadd
模式串: ababa
j = 5的情况
主串S: ababe
模式串: ababa
• 当 j=6时, j 由 1到 j-1 范围内有字符 “ababa”,前缀 “aba” 与 后缀 “aba” 相等,那么此时
k = 4; next[6] = 4;
• 当 j=7时, j 由 1到 j-1 范围内有字符 “ababaa”,前缀 “a” 与 后缀 “a” 相等,那么此时 k =
2; next[7] = 2;
• 当 j=8时, j 由 1到 j-1 范围内有字符 “ababaaa”,前缀 “a” 与 后缀 “a” 相等,那么此时 k =
2; next[8] = 2;
• 当 j=9时, j 由 1到 j-1 范围内有字符 “ababaaab”,前缀 “ab” 与 后缀 “ab” 相等,那么此时
k = 3; next[9] = 3;
T = “aaaaaaaab”
解读:
• 当 j=1时, next[1] = 0
• 当 j=2时, j 由 1到 j-1 范围内只有字符 “a”, 属于其他情况 next[2] = 1;
• 当 j=3时, j 由 1到 j-1 范围内有字符 “aa”, 前缀 ”a” 与 后缀“a” 相等,所以k = 2; next[3]
= 2;
• 当 j=4时, j 由 1到 j-1 范围内有字符 “aaa”, 前缀 ”aa” 与 后缀“aa” 相等,所以k = 3;
next[4] = 3;
• 当 j=5时, j 由 1到 j-1 范围内有字符 “aaaa”, 前缀 ”aaa” 与 后缀“aaa” 相等,所以k = 4;
next[5] = 4;
当 j=6时, j 由 1到 j-1 范围内有字符 “aaaaa”, 前缀 ”aaaa” 与 后缀“aaaa” 相等,所以k =
5; next[6] = 5;
• 当 j=7时, j 由 1到 j-1 范围内有字符 “aaaaaa”, 前缀 ”aaaaa” 与 后缀“aaaaa” 相等,所
以k = 6; next[7] = 6;
• 当 j=8时, j 由 1到 j-1 范围内有字符 “aaaaaaa”, 前缀 ”aaaaaa” 与 后缀“aaaaaa” 相等,
所以k = 7; next[8] = 7;
• 当 j=9时, j 由 1到 j-1 范围内有字符 “aaaaaaaa”, 前缀 ”aaaaaaa” 与 后缀“aaaaaaa” 相
等,所以k = 8; next[9] = 8;
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
生成一个其值等于chars的串T
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars); //第0项存储 字符串的长度
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
Status ClearString(String S)
{
S[0]=0;/* 令串长为零 */
return OK;
}
//输出字符串T
void StrPrint(String T)
{
int i;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("\n");
}
返回串的元素个数
int StrLength(String S)
{
return S[0];
}
一、KMP 模式匹配算法
1.通过计算返回子串T的next数组;
注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
void get_next(String T,int *next){
int i,j;
j = 1;
i = 0;
next[1] = 0;
//abcdex
//遍历T模式串, 此时T[0]为模式串T的长度;
//printf("length = %d\n",T[0]);
while (j < T[0]) {
//printf("i = %d j = %d\n",i,j);
if(i ==0 || T[i] == T[j]){
//T[i] 表示后缀的单个字符;
//T[j] 表示前缀的单个字符;
++i;
++j;
next[j] = i;
printf("next[%d]=%d\n",j,next[j]);
}else
{
//如果字符不相同,则i值回溯;
i = next[i];
}
}
}
StrAssign(s1,"abbbabekb");
printf("子串为: ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf("Next为: ");
子串为: abbbabekb
next[2]=1
next[3]=1
next[4]=1
next[5]=1
next[6]=2
next[7]=3
next[8]=1
next[9]=1
输出Next数组值
void NextPrint(int next[],int length)
{
int i;
for(i=1;i<=length;i++)
printf("%d",next[i]);
printf("\n");
}
KMP 匹配算法(1)
返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP(String S,String T,int pos){
//i 是主串当前位置的下标准,j是模式串当前位置的下标准
int i = pos;
int j = 1;
//定义一个空的next数组;
int next[MAXSIZE];
//对T串进行分析,得到next数组;
get_next(T, next);
count = 0;
//注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
//若i小于S长度并且j小于T的长度是循环继续;
while (i <= S[0] && j <= T[0]) {
//如果两字母相等则继续,并且j++,i++
if(j == 0 || S[i] == T[j]){
i++;
j++;
}else{
//如果不匹配时,j回退到合适的位置,i值不变;
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];
}else{
return -1;
}
}
StrAssign(s1,"abcababca");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"caba");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
主串为: abcababca
子串为: abcdex
next[2]=1
next[3]=1
next[4]=1
next[5]=1
next[6]=1
主串和子串在第-1个字符处首次匹配（KMP算法）[返回位置为负数/-1表示没有匹配]
主串为: abcababca
子串为: bcab
next[2]=1
next[3]=1
next[4]=1
主串和子串在第2个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配]
二、KMP 模式匹配算法 优化
求模式串T的next函数值修正值并存入nextval数组中;
void get_nextVal(String T,int *nextVal){
int i,j;
j = 1;
i = 0;
nextVal[1] = 0;
while (j < T[0]) {
if (i == 0 || T[i] == T[j]) {
++j;
++i;
//如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
if(T[i] != T[j])
nextVal[j] = i;
else
//如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
nextVal[j] = nextVal[i];
}else{
i = nextVal[i];
}
}
}
StrAssign(s1,"abbbabekb");
printf("子串为: ");
NextPrint(p,StrLength(s1));
t=(int*)malloc((i+1)*sizeof(int));
get_nextVal(s1, t);
printf("NextVal为: ");
NextPrint(t,StrLength(s1));
printf("\n");
子串为: abbbabekb
NextVal为: 011101311
返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回-1;
int Index_KMP2(String S,String T,int pos){
//i 是主串当前位置的下标准,j是模式串当前位置的下标准
int i = pos;
int j = 1;
//定义一个空的next数组;
int next[MAXSIZE];
//对T串进行分析,得到next数组;
get_nextVal(T, next);
count = 0;
//注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
//若i小于S长度并且j小于T的长度是循环继续;
while (i <= S[0] && j <= T[0]) {
//如果两字母相等则继续,并且j++,i++
if(j == 0 || S[i] == T[j]){
i++;
j++;
}else{
//如果不匹配时,j回退到合适的位置,i值不变;
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];
}else{
return -1;
}
}
StrAssign(s1,"abcababca");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"caba");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP2(s1, s2, 1);
printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
主串为: abcababca
子串为: caba
主串和子串在第3个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配]
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, KMP匹配算法实现!\n");
int i,*p,*t;
String s1,s2;
int Status;
/*关于next数组的求解*/
StrAssign(s1,"abbbabekb");
printf("子串为: ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf("Next为: ");
//
StrAssign(s1,"abbbabekb");
printf("子串为: ");
NextPrint(p,StrLength(s1));
t=(int*)malloc((i+1)*sizeof(int));
get_nextVal(s1, t);
printf("NextVal为: ");
NextPrint(t,StrLength(s1));
printf("\n");
//KMP算法调用
StrAssign(s1,"abcababca");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"caba");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP2(s1, s2, 1);
printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
//
// StrAssign(s1,"abccabcceabc");
// printf("主串为: ");
// StrPrint(s1);
// StrAssign(s2,"abcce");
// printf("子串为: ");
// StrPrint(s2);
// Status = Index_KMP(s1,s2,1);
// printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
// Status = Index_KMP2(s1, s2, 1);
// printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
//
// StrAssign(s1,"aaaabcde");
// printf("主串为: ");
// StrPrint(s1);
// StrAssign(s2,"aaaaax");
// printf("子串为: ");
// StrPrint(s2);
// Status = Index_KMP(s1,s2,1);
// printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
// Status = Index_KMP2(s1, s2, 1);
// printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
//
return 0;
}
网友评论