KMP算法
KMP算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，每一趟匹配过程中出现字符比较不等时候，不需要回溯i指针，而是利用已经得到的“部分匹配的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
我们先来看几个例子
第一个例子 主串S为：" ACABAABAABCACAABC" 子串T为：" ABAABCAC"
第一次比较：将子串T放在第一位与主串比较，发现子串第二位与主串第二位不等。第二次比较：将子串放T放在上一次不相等的位置，再次进行比较，发现子串第一位就与主串不相等。子串向后移动一位再次进行比较。第三次比较：这次是子串的第六位与主串第八位不相等，这时并没有把子串移置到不相等的位置上。仔细观察，如果子串移置主串第8位上 那么这时字符串匹配效果是失败的，字符串找不到与之相对应的主串字符，出现了漏查的情况。所以说子串第一个字符 回溯的位置另有蹊跷 。
匹配次数子串起始位置失败位置
第一次12第二次22第三次38第四次6-
第二个例子 主串为：" ABCABDABCEABDBCBD" 子串为：" ABCEABBD"
匹配次数子串起始位置失败位置
第一次14第二次46第三次66第四次713第五次1113第六次1313第O^O次……
那么子串 回溯的位置另有蹊跷 ，究竟是什么呢。 这里另有蹊跷的意思是，子串需要观察自身结构，若自身有重复的结构，需要回溯到重复位置的后者不然会造成字符串匹配缺失的情况。这里科学家们引入了模式串next。
引入模式串next
模式串是对于子串而言，专门计算子串的前缀后缀重复字符个数
结合next[j]再来看例一
匹配次数子串起始位置子串失败位置失败位置next[j]
第一次1221第二次2120第三次3683第四次6---
现在是否发现了回溯位置与next[j]值的关系了呢？
next[j]代码实现
void get_next(SString T
, int next
[])
{
int i
= 1;
next
[1] = 0;
int j
= 0;
while (i
< T
.length
)
{
if (j
== 0 || T
.ch
[i
] == T
.ch
[j
])
{
++i
; ++j
;
next
[i
] = j
;
}
else
j
= next
[j
];
}
}
完整测试next代码
#include<iostream>
using namespace std
;
#define MAXLEN 100
typedef struct {
char ch
[MAXLEN
+ 1];
int length
;
}SString
;
void get_next(SString T
, int next
[])
{
int i
= 1;
next
[1] = 0;
int j
= 0;
cout
<< "i = " << i
<< " " << "j = " << j
<<" next["<<i
<<"] = "<<0<<endl
;
while (i
< T
.length
)
{
if (j
== 0 || T
.ch
[i
] == T
.ch
[j
])
{
++i
; ++j
;
next
[i
] = j
;
cout
<< "i = " << i
<< " " << "j = " << j
;
cout
<< " next[" << i
<< "] = "<< j
<<endl
;
}
else
{
cout
<< "i = " << i
;
cout
<< " j = " << next
[j
] << endl
;
j
= next
[j
];
}
}
}
int main()
{
SString s
= {" ABAABCAC",8};
int* next
;
next
= (int*)malloc(s
.length
* sizeof(int));
get_next(s
, next
);
cout
<< next
[1]<<" "<< next
[2] << " " << next
[3] << " " << next
[4] << " " << next
[5] << endl
;
}
字符串第一个元素一般存储字符串的大小。T.ch[0]为数字的ASCII码值，注意修改！
KMP代码实现
int Index_KMP(SString S
, SString T
, int next
[])
{
int i
= 1;
int j
= 1;
while (i
<= S
.length
&& j
<= T
.length
)
{
if (j
== 0 || S
.ch
[i
] == T
.ch
[j
])
{
++i
;
++j
;
}
else
j
= next
[j
];
}
if (j
> T
.length
)
return i
- T
.length
;
else
return 0;
}
主串回溯：
不回溯 子串回溯：
j=next[j]
回溯后的j=1代表从子串第一个位置与主串[i]相匹配，若不匹配—>j=0—>j++，i++进行下一次匹配 回溯后的j=3代表从子串第三个位置与主串[i]相匹配
KMP算法完整测试代码
#include<iostream>
using namespace std
;
#define MAXLEN 100
typedef struct {
char ch
[MAXLEN
+ 1];
int length
;
}SString
;
void get_next(SString T
, int next
[])
{
int i
= 1;
next
[1] = 0;
int j
= 0;
while (i
< T
.length
)
{
if (j
== 0 || T
.ch
[i
] == T
.ch
[j
])
{
++i
; ++j
;
next
[i
] = j
;
}
else
{
j
= next
[j
];
}
}
}
int Index_KMP(SString S
, SString T
, int next
[])
{
int i
= 1;
int j
= 1;
while (i
<= S
.length
&& j
<= T
.length
)
{
if (j
== 0 || S
.ch
[i
] == T
.ch
[j
])
{
++i
;
++j
;
}
else
j
= next
[j
];
}
if (j
> T
.length
)
return i
- T
.length
;
else
return 0;
}
int main()
{
SString s
= {" ABAABCAC",8};
int* next
;
next
= (int*)malloc(s
.length
* sizeof(int));
get_next(s
, next
);
SString t
= { " CAC",3 };
int n
= Index_KMP(s
, t
, next
);
cout
<< "\"CAC\"位于\"ABAABCAC\"的第" << n
<< "个位置！";
return 0;
}
