KMP模式匹配算法 C++实现

KMP模式比配算法

// KMP模式比配算法.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#define MAX 1000
using namespace std;

char s[MAX],t[MAX];
int next[MAX];

//
void ComputeNext(char *t,int *next,const int lenT)
{
int i,j;
next[0] = -1;
i = 0;
j = -1;
while(i<lenT)
{
while(j>=0&&t[i] !=t[j] )
j = next[j];
j++;
i++;
//next[i] = j;
//改进
if(t[i]==t[j])
next[i] = next[j];
else
next[i] = j;
}
}

//
int KMP(char *s,char *t,int *next,const int lenS,const int lenT)
{
int i,j;
i=j=-1;
while(i<lenS&&j<lenT)
{
if((j==-1)||(s[i]==t[j]))
{
i++;
j++;
}
else
j = next[j];
}
if(j>=lenT)
return i-lenT+1;
else
return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数：";
cin>>cases;
while(cases--)
{
cout<<"请输入主串:"<<endl;
cin>>s;
int lenS = strlen(s);
while(1)
{
cout<<"请输入需要匹配的模式串(以0结束):"<<endl;
cin>>t;
if(!strcmp(t,"0"))
break;
int lenT = strlen(t);
for(int i=0;i<lenT;i++)
next[i] = -1;
ComputeNext(t,next,lenT);
int pos = KMP(s,t,next,lenS,lenT);
if(pos==0)
cout<<"没有匹配项!"<<endl;
else
cout<<"匹配的开始位置为:"<<pos<<endl;
}
}
system("pause");
return 0;
}

---------------------------------------------------程序测试---------------------------------------------------

请输入案例的个数：1
请输入主串:
heyongluoyao8
请输入需要匹配的模式串(以0结束):
he
匹配的开始位置为:1
请输入需要匹配的模式串(以0结束):
yong
匹配的开始位置为:3
请输入需要匹配的模式串(以0结束):
luo
匹配的开始位置为:7
请输入需要匹配的模式串(以0结束):
luoyao
匹配的开始位置为:7
请输入需要匹配的模式串(以0结束):
lao
没有匹配项!
请输入需要匹配的模式串(以0结束):
0
请按任意键继续. . .