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

一时失言乱红尘 2022-05-15 13:23 174阅读 0赞

**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  
请按任意键继续. . .**