串的模式匹配算法
#include <cstdlib>
#include <iostream>
#include <string>
#define MaxSize 15
using namespace std;
int next[9],nextval[9];
int KMPIndex(string S, int start,string T, int next[ ])
{
//利用模式串T的next函数求T在主串S第pos个字符之后的位置
// 的KMP算法。其中,T非空,1<=pos<=S.length;
int i=start,j=1,v;
while ( i<=S.length()&&j<=T.length()) {
if (j==0|| S[i] == T[j] )
{
++i; ++j; //继续比较后继字符
}
else j=next[j]; //模式串向右移动
}
if(j>T.length()) v=i-T.length(); //匹配成功
else v=0; //匹配不成功
return v;
}
void GetNext(string T)
{
//球模式串T的next函数值并存入数组next
int i = 1, j = 0; next[1] = 0;
while(i< T.size()){
if(j==0 ||T[i]==T[j])
{++i; ++j; next[i]=j; }
else j=next[j];
}
}
void GetNextval(string T)
{
//球模式串T的next函数值并存入数组nextval
int i = 1, j = 0; next[1] = 0;
while(i< T.size()){
if(j==0 ||T[i]==T[j])
{
++i; ++j;
if (T[i]!=T[j]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}
}
//主函数
int main(void)
{
string S="acabaabaabcacaabc", T ="3abaabcac";
int pos;
printf("调用GetNext得到的next数组元素");
GetNext(T);
for(int i=1;i<9;i++){
printf("next=%d\n",next[i]);
}
printf("调用GetNextval得到的nextval数组元素");
GetNextval(T);
for(int i=1;i<9;i++){
printf("next=%d\n",nextval[i]);
}
pos = KMPIndex(S, 1, T, next);
printf("pos = %d\n", pos);
system("PAUSE");
return EXIT_SUCCESS;
}
结果:
- 大小: 8.4 KB
分享到:
相关推荐
字符串模式匹配算法的改进研究.pdf 字符串模式匹配算法的改进研究.pdf
基于字符串模式匹配算法的病毒感染检测问题——C语言实现。
《数据结构(C语言版 第2版)》严蔚敏 实验四 基于字符串模式匹配算法的病毒感染检测问题,含实验报告
实验二 串模式匹配算法(串实验) 实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主串、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法...
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
C/C++实现串匹配算法,包括源代码和实验报告。实现了串的创建,查看,修改,朴素的模式匹配算法,kmp算法和kmp改进算法。
KMP字符串模式匹配算法,内是ppt讲解,比较通俗易懂了。。
用C++实现BM的字符串模式匹配算法,两个代码分别实现坏字符规则和好后缀规则
关于KMP_字符串模式匹配算法的教学课件,详细讲解了Kmp 的原理与不足和改进
字符串的模式匹配算法——KMP的C++实现。
提供了一种新的字符串模式匹配算法的实现,而常规算法往往低效.字符串模式匹配算法是程序开发过程中应用非常广的重要算法.
Kmp字符串模式匹配算法.doc
一种改进的串的模式匹配算法的探讨,穆维友,吴泽平,串的模式匹配算法一直都是计算机科学领域的研究焦点之一。本文首先分析了BF、KMP、BM三种算法,并提出了一种改进的Sundaynew算法,给��
KMP字符串模式匹配算法[文].pdf
基于C语言的串模式匹配算法
《KMP字符串模式匹配算法》教学课例[参照].pdf
《KMP字符串模式匹配算法》教学课例[归纳].pdf
一种新的串模式匹配算法,韩雷钧,张凯,模式的匹配算法一直是计算机搜索领域的研究的重点工程。本文首先分析了传统的蛮力字符串匹配和增强型的Boyer-Moore算法,并提出了一�