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
请按任意键继续. . .
分享到:
相关推荐
KMP模式匹配C描述算法。
字符串的模式匹配算法——KMP的C++实现。
KMP 模式匹配算法实例 C++源码 字符串查找
C++实现kmp字符串匹配算法,算法思想: *KMP算法的思想就是在匹配过程称若发生不匹配的情况 *如果next[j]>=0则目标串的指针i不变将模式串的指针j移动到next[j]的位置继续进行匹配 *若next[j]=-1则将...
里面包含完整的可运行的程序,课设说明书。...在程序设计中,采用了串的KMP模式匹配算法实现了子串的定位操作。程序通过调试运行,初步实现了设计目标,并且经过适当完善后,将可以解决实际问题。 里面
基于字符串模式匹配算法的病毒感染检测问题——C语言实现。
《数据结构》串章节字符串的模式匹配KMP算法详解
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
串的匹配模式,C++算法的实现 用到了KMP算法
C/C++实现串匹配算法,包括源代码和实验报告。实现了串的创建,查看,修改,朴素的模式匹配算法,kmp算法和kmp改进算法。
暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个...
利用C++实现以下经典数据结构与算法:线性表(顺序表、链表、静态链表、三元组)、栈(双栈、共享栈)、队列(任务调度、循环队列、双向队列、链队列)、数组(特殊矩阵、稀疏矩阵压缩)、串(朴素模式匹配、KMP算法...
程序开发过程中的字符串匹配算法很多,这里出了算法的程序源代码,包括C#,C++, Delphi代码,大家直接下载就可以拷贝到自己程序中使用。
相比于朴素的字符串匹配算法,KMP算法的时间复杂度更低,特别是在模式串较长或者需要多次匹配的情况下,KMP算法能够显著提高匹配效率。 总的来说,KMP算法是一种非常实用的字符串匹配算法,被广泛应用于各种文本...
KMP算法是一种高效的字符串匹配算法,全称为Knuth-Morris-Pratt算法。该算法由D.E.Knuth,J.H.Morris和V.R.Pratt提出,其核心思想是通过预处理模式串(也称子串)的部分匹配信息,在匹配失败时尽可能地移动模式串的...
用c++求出一个字符串字串在主串中的位置,分别用BF算法和KMP算法
严蔚敏版数据结构中的KMP算法的C++语言实现,有结果截图
KMP算法和朴素算法,codeblocks环境下编译,自己再调试调试吧
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。先来看一个简单匹配算法的函数:此算法的思想是...