本文目录一览：
- 1、KMP算法，输三组主串S和模式串P，输出模式串的Next(j)函数值，及该P在S中的位置的定
- 2、KMP模式匹配算法是什么？
- 3、KMP算法的原理及其应用
- 4、KMP算法详细代码
- 5、kmp算法详解
- 6、数据结构里实现KMP算法
KMP算法，输三组主串S和模式串P，输出模式串的Next(j)函数值，及该P在S中的位置的定
KMP算法查找串S中含串P的个数count
#include iostream
#include stdlib.h
#include vector
using namespace std;
inline void NEXT(const string T,vectorint next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;iT.size();i++ ){
int j=next[i-1];
while(T[i]!=T[j+1] j=0 )
j=next[j] ; //递推计算
if(T[i]==T[j+1])next[i]=j+1;
else next[i]=0; //
}
}
inline string::size_typeCOUNT_KMP(const string S,
const string T)
{
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空，
vectorint next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;indexS.size();++index){
int pos=0;
string::size_type iter=index;
while(posT.size() iterS.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="abaabcacabaabcacabaabcacabaabcacabaabcac";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
coutcountendl;
system("PAUSE");
return 0;
}
KMP模式匹配算法是什么？
KMP模式匹配算法是一种改进算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的，因此人们称它为“克努特－莫里斯－普拉特操作”，简称KMP算法。此算法可以在O（n＋m）的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程出现字符不相等时，主串指针i不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指针j向右“滑动”尽可能远的一段距离后，继续进行比较。
1.KMP模式匹配算法分析回顾图4－5所示的匹配过程示例，在第三趟匹配中，当i＝7、j＝5字符比较不等时，又从i＝4、j＝1重新开始比较。然而，经仔细观察发现，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中的第4、5和6个字符必然是b、c和a（即模式串第2、第2和第4个字符）。因为模式中的第一个字符是a，因此它无须再和这三个字符进行比较，而仅需将模式向右滑动2个字符的位置进行i＝7、j＝2时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右移动两个字符的位置继续进行i＝2、j＝1时的字符比较。由此，在整个匹配过程中，i指针没有回溯，如图1所示。
图1改进算法的模式匹配过程示意
KMP算法的原理及其应用
KMP算法是通过分析子串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后再上面的算法中使用。
讲解一下：
当我们分析一个子串时，例如：abcabcddes. 需要分析一下，每个字符x前面最多有多少个连续的字符和字符串从初始位置开始的字符匹配。然后+1就行了（别忘了，我们的字符串都是从索引1开始的）当然，不要相同位置自己匹配，默认第一个字符的匹配数是0。
定义如下：设字符串为 x1x2x3...xn ,其中x1，x2，x3，... xi，... xn均是字符，设ai为字符xi对应的整数。则a=m，当且仅当满足如下条件：字符串x1x2...xm equals 字符串x(i-m+1)...xi-1 xi 并且x1x2...xm x(m+1) unequals x(i-m) x(i-m+1)...xi-1 xi。
举例如下：
abcabcddes
0111234111
|----------------------默认是0
--| | |-----------------不能自己相同字符匹配，所以这里者能认为是没有所以是0+1 =1
------| | |-----------前面的字符和开始位置的字符相同，所以是2,3,4
-----------| | | |-------不匹配只能取1。
希望能明白的是，如果开始字符是 Ch1的话，那么我们就是要在串中第2个Ch1后面的位置开始自己和自己匹配，计算最大的吻合度。
程序写出来就是：
void GetNext(char* T, int *next)
{
int k=1,j=0;
next[1]=0;
while( k〈 T[0] ){
if (j ==0 || T[k] == T[j])
{
++k;
++j;
next[k] = j;
}
else j= next[j];
}
}
但是这个不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下：
void GetNextEx(char *T, char *next)
{
int i=k,j=0; next[1] = 0;
while(k T[0])
{
if (j == 0 || T[k] == T[j])
{
++k; ++j;
if (T[k] == T[j])
next[k] = next[j];
else
next[k] = j;
}
else j = next[j];
}
}
现在我们已经可以得到这个next字符串的值了，接下来就是KMP算法的本体了：
相当简单：
int KMP(char* S, char* T, int pos)
{
int k=pos, j=1;
while (k){
if (S[k] == T[j]){ ++k; ++j; }
else j = next[j]
}
if (jT[0]) return k-T[0];
else return 0;
}
和朴素算法相比，只是修改一句话而已，但是算法复杂度从O(m*n) 变成了：O(m)
KMP算法详细代码
KMP.java
源代码为：
package algorithm.kmp;
/**
* KMP算法的Java实现例子与测试、分析
* @author 崔卫兵
* @date 2009-3-25
*/
public class KMP {
/**
* 对子串加以预处理，从而找到匹配失败时子串回退的位置
* 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率
* 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组
* @param B，待查找子串的char数组
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循环一次，就会找到一个回退位置
for(int i=1;isize;i++){
//当找到第一个匹配的字符时，即j0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j0 B[j]!=B[i]){
j=P[j];
}
//p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化
if(B[j]==B[i]){
j++;
}
//找到一个回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}
/**
* KMP实现
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;iparSize;i++){
//当找到第一个匹配的字符时，即j0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j0 B[j]!=A[i]){
//找到合适的回退位置
j=P[j-1];
}
//p2 找到一个匹配的字符
if(B[j]==A[i]){
j++;
}
//输出匹配结果，并且让比较继续下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}
public static void main(String[] args) {
//回退位置数组为P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");
//回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit");
//回退位置数组为P[0, 0, 0]
kmp("测试汉字的匹配，崔卫兵。这个会匹配1次","崔卫兵");
//回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("这个会匹配0次","it1it1it1");
}
}
kmp算法详解
KMP模式匹配算法
KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的明[4]。
求得模式的特征向量之后，基于特征分析的快速模式匹配算法(KMP模式匹配算法)与朴素匹配算法类似，只是在每次匹配过程中发生某次失配时，不再单纯地把模式后移一位，而是根据当前字符的特征数来决定模式右移的位数[3]。
include "string. h"
#includeassert. h
int KMPStrMatching(String T, String P, int. N, int startIndex)
{int lastIndex=T.strlen() -P.strlen();
if((1 astIndex- startIndex)0)//若 startIndex过大,则无法匹配成功
return (-1);//指向P内部字符的游标
int i;//指向T内部字符的游标
int j=0;//指向P内部字符的游标
for(i= startIndex; i T.strlen(); i++)
{while(P[j]!=T[i] j0)
j=N[j-1];
if(P[j]==T[i])
j++;
if(j ==P.strlen())
return(1-j+1);//匹配成功,返回该T子串的开始位置
}
return (-1);
}
数据结构里实现KMP算法
KMP算法的C语言实现2007-12-10 23:33
基本思想：
这种算法是D.E.Knuth 与V.R.Pratt和J.H.Morris同时发现的，因此人们称为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。
其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
#include stdio.h
#include string.h
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);
char s[10]="abcacbcba";
char t[4]="bca";
int next[4];
int pos=0;
int main()
{
int n;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
return 0;
}
int index_KMP(char *s,char *t,int pos)
{
int i=pos,j=1;
while (i=(int)strlen(s)j=(int)strlen(t))
{
if (j==0||s[i]==t[j-1])
{
i++;
j++;
}
else j=next[j];
}
if (j(int)strlen(t))
return i-strlen(t)+1;
else
return 0;
}
void get_next(char *t,int *next)
{
int i=1,j=0;
next[0]=next[1]=0;
while (i(int)strlen(t))
{
if (j==0||t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
}
