#include<stdio.h>
#define N1 11
#define N2 6
void kmp(char *p,char *q,int *next);
void basicIndex(char *p,char *q){
int i=0,j=0,pos;
while(i<N1&&j<N2){
if(p[i]==q[j])
{
i++;
j++;
}else{
i=i-j+1;
j=0;
}
}
if(j>=N2){
pos=i-j;
}else
pos=-1;
printf("%d",pos);
}
//basic next of KMP
void getNext(char *p,char *q){
int i=0,j=-1,next[N2];
next[0]=-1;
while(i<N2){
if(j==-1||q[i]==q[j]){
i++;
j++;
next[i]=j;
}else{
j=next[j];
}
}
kmp(p,q,next);
}
//improved nextvar of KMP
void getNextVar(char *p,char *q){
int i=0,j=-1,nextvar[N2];
nextvar[0]=-1;
while(i<N2){
if(j==-1||q[i]==q[j]){
i++;
j++;
if(q[i]!=q[j]){
nextvar[i]=j;
}else{
nextvar[i]=nextvar[j];
}
}else{
j=nextvar[j];
}
}
kmp(p,q,nextvar);
}
void kmp(char *p,char *q,int *next){
int i=0,j=0,pos=0;
while(i<N1&&j<N2){
if(j==-1||p[i]==q[j]){
i++;
j++;
}else{
j=next[j];
}
}
if(j>=N2){
pos=i-j;
}else{
pos=-1;
}
printf("%d",pos);
}
void main(){
char *p={"00000000001"};
char *q={"000001"};
getNext(p,q);
}
分享到:
相关推荐
基于字符串模式匹配算法的病毒感染检测问题——C语言实现。
字符串模式匹配算法的改进研究.pdf 字符串模式匹配算法的改进研究.pdf
《数据结构(C语言版 第2版)》严蔚敏 实验四 基于字符串模式匹配算法的病毒感染检测问题,含实验报告
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
KMP字符串模式匹配算法,内是ppt讲解,比较通俗易懂了。。
用C++实现BM的字符串模式匹配算法,两个代码分别实现坏字符规则和好后缀规则
关于KMP_字符串模式匹配算法的教学课件,详细讲解了Kmp 的原理与不足和改进
字符串的模式匹配算法——KMP的C++实现。
提供了一种新的字符串模式匹配算法的实现,而常规算法往往低效.字符串模式匹配算法是程序开发过程中应用非常广的重要算法.
Kmp字符串模式匹配算法.doc
KMP字符串模式匹配算法[文].pdf
《KMP字符串模式匹配算法》教学课例[参照].pdf
《KMP字符串模式匹配算法》教学课例[归纳].pdf
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数: ...
合肥工业大学《程序设计与算法训练》(即《数据结构》课程设计)的题目“字符串模式匹配算法比较”可以参考本项目。(最近闲得无聊练手Qt做的,毕业老学长奉上,蛤蛤蛤!)
程序开发过程中的字符串匹配算法很多,这里出了算法的程序源代码,包括C#,C++, Delphi代码,大家直接下载就可以拷贝到自己程序中使用。
收集了网上的相关的论文和文章,希望对在相关方面有兴趣的有帮助
大连理工大学数据结构上机题字符串朴素模式匹配算法字符串朴素模式匹配算法字符串朴素模式匹配算法字符串朴素模式匹配算法