模式匹配算法
㈠ KMP模式匹配算法
这里有个相似的问题，也是我回答的，讲了原理
http://..com/question/329386416.html
如果你只要代码的话
一个简单的代码
#include <stdio.h>
#include <string.h>
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);
char s[10]="abcacbcba";
char t[4]="bca";
int next[4];
int pos=0;
int main()
{
int n;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
return 0;
}
int index_KMP(char *s,char *t,int pos)
{
int i=pos,j=1;
while (i<=(int)strlen(s)&&j<=(int)strlen(t))
{
if (j==0||s[i]==t[j-1])
{
i++;
j++;
}
else j=next[j];
}
if (j>(int)strlen(t))
return i-strlen(t)+1;
else
return 0;
}
void get_next(char *t,int *next)
{
int i=1,j=0;
next[0]=next[1]=0;
while (i<(int)strlen(t))
{
if (j==0||t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
}
㈡ 模式匹配算法的设计与实现
你做出来了么？同求啊。。。。。。
㈢ 用简单的模式匹配算法需要多少次比较能
简单的模式匹配算法时间复杂度是大O(n+m)次。
㈣ 求助！！！！！！！模式匹配和KMP算法
这个题目最难的是KMP算法和实现。其他的书本上都有的。
我自己写的个程序：
测试结果如下：
13113113111
at 37
贴上源代码：
#include"stdio.h"
#include "conio.h"
#include "stdio.h"
#include "math.h"
int result;
char pat[]="13113113111";
char str[]="";
int next[7];
void getNext(char pat[], int next[])
{
int j = 0;
int k = -1;
next[0] = -1;
while (pat[j])
{
if ( k == -1 || pat[j] == pat[k])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k];
}
}
}
int KMP(char *str1, char*pat, int *next)
{
int i=0,j=0;
while(str[i])
{
if(pat[j]==0)
return i-j;
if(j==0 || str[i]==pat[j])
{
++i;
++j;
}else
j=next[j];
}
if(pat[j]==0)
return i-j;
return -1;
}
int main(int argc, char* argv[])
{
int i;
getNext(pat,next);
result=KMP(str,pat,next);
printf("%s\n",str);
for(i=0;i<result;i++) printf(" ");
printf("%s\n",pat);
printf("at %d\n",result);
getch();
return 0;
}
祝你好运！
㈤ 串模式匹配算法
你的财富太低了。。这个写起来貌似很多东东的
不过我想问下KMP改进算法（NextVal[]）是什么？
㈥ KMP模式匹配算法是什么
KMP模式匹配算法是一种改进算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的，因此人们称它为“克努特－莫里斯－普拉特操作”，简称KMP算法。此算法可以在O（n＋m）的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程出现字符不相等时，主串指针i不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指针j向右“滑动”尽可能远的一段距离后，继续进行比较。
1.KMP模式匹配算法分析回顾图4－5所示的匹配过程示例，在第三趟匹配中，当i＝7、j＝5字符比较不等时，又从i＝4、j＝1重新开始比较。然而，经仔细观察发现，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中的第4、5和6个字符必然是b、c和a（即模式串第2、第2和第4个字符）。因为模式中的第一个字符是a，因此它无须再和这三个字符进行比较，而仅需将模式向右滑动2个字符的位置进行i＝7、j＝2时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右移动两个字符的位置继续进行i＝2、j＝1时的字符比较。由此，在整个匹配过程中，i指针没有回溯，如图1所示。
图1改进算法的模式匹配过程示意
㈦ 串的模式匹配算法，求编程
#include<stdio.h>
void getnext(const char c[],int next[])
{
int j=0,k=-1;
next[0]=-1;
while(c[j]!='\0')
{
if(k==-1||c[j]==c[k])
{
j++;
k++;
if(c[j]!=c[k])
next[j]=k;
else
next[j]=next[k];
}
else
k=next[k];
}
}
int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{
if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//
return -1;//空指针或空串，返回-1。
int len=0;
const char * c=Pattern;
while(*c++!='\0')//移动指针比移动下标快。
{
++len;//字符串长度。
}
int *next=new int[len+1];
getnext(Pattern,next);//求Pattern的next函数值
int index=0,i=0,j=0;
while(Text[i]!='\0' && Pattern[j]!='\0' )
{
if(Text[i]== Pattern[j])
{
++i;// 继续比较后继字符
++j;
}
else
{
index += j-next[j];
if(next[j]!=-1)
j=next[j];// 模式串向右移动
else
{
j=0;
++i;
}
}
}
delete []next;
if(Pattern[j]=='\0')
return index;// 匹配成功
else
return -1;
}
int main()
{
char clong[100],cshort[20]="abcac";
int next[20];
scanf("%s",clong);
scanf("%s",cshort);
printf("%d",KMP(clong,cshort));
}
㈧ 串模式匹配算法（C语言）100分悬赏
第一个朴素算法:
1.普通的串模式匹配算法:
int index(char s[],char t[],int pos)
/*查找并返回模式串T在S中从POS开始的位置下标,若T不是S的子串.则返回-1.*/
{
int i,j,slen,tlen;
i=pos;j=0; //i,j分别指示主串和模式串的位置.
slen=strlen(s);tlen=strlen(t); //计算主串和模式串的长度.
while(i<slen && j<tlen)
{
if(s[i]==t[j]) {i++;j++;}
else {i=i-j+1;j=0;}
}
if(j>=tlen) return i-tlen;
return -1;
}
第二个KMP算法.该算法支持从主串的任意位置开始搜索.
2.KMP算法:
//求模式串的next函数.
void get_next(char *p,int next[])
{
int i,j,slen;
slen=strlen(p);i=0;
next[0]=-1;j=-1;
while(i<slen)
{
if(j==-1||p[i]==p[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}
//KMP模式匹配算法
int index_kmp(char *s,char *p,int pos,int next[])
/* 利用模式串P的NEXT函数,求P在主串S中从第POS个字符开始的位置*/
/*若匹配成功.则返回模式串在主串中的位置下标.否则返回-1 */
{
int i,j,slen,plen;
i=pos-1;j=-1;
slen=strlen(s);plen=strlen(p);
while(i<slen && j<plen)
{
if(j==-1||s[i]==p[j]) {++i;++j;}
else j=next[j];
㈨ 《数据结构（C语言版）》之“串的模式匹配算法”
# include <string.h>
# include <stdio.h>
# include <stdlib.h>
# define OK 1
# define ERROR 0
typedef int Status;
//串的定长顺序存储结构
# define MAX_STR_LEN 40
typedef char SString[MAX_STR_LEN + 1];//0号单元存放串的长度
Status StrAssign(SString T,char * chars)//生成一个其值等于chars的串T
{
int i;
if (strlen(chars) > MAX_STR_LEN)
{
return ERROR;
}
else
{
T[0] = strlen(chars);
for (i=1; i<=T[0]; ++i)
{
T[i] = * (chars + i - 1);
}
return OK;
}
}
//返回串S的元素的个数
int StrLength(SString S)
{
return S[0];
}
//用Sub返回串S的自第pos个字符起长度为len的子串
Status SubString(SString Sub,SString S,int pos,int len)
{
int i;
if (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
{
return ERROR;
}
for (i=1; i<=len; ++i)
{
Sub[i] = S[pos+i-1];
}
Sub[0] = len;
return OK;
}
//输出字符串T
void StrPrint(SString T)
{
int i;
for (i=1; i<=T[0]; ++i)
{
printf("%c ",T[i]);
}
printf("\n");
}
//求模式串T的next函数值并存入数组next
void get_next(SString T,int next[])
{
int i = 1,j = 0;
next[1] = 0;
while (i < T[0])
{
if (j==0 || T[i]==T[j])
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];
}
}
}
//求模式串T的next函数修正值并存入数组nextval
void get_nextval(SString T,int nextval[])
{
int i = 1,j = 0;
nextval[1] = 0;
while (i < T[0])
{
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];
}
}
}
//利用模式串T的next函数求T在主串S中第pos字符之后的位置的KMP算法
//1=<pos=<StrLength(S)
int Index_KMP(SString S,SString T,int pos,int next[])
{
int i = pos,j = 1;
while (i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if (j > T[0])
{
return i - T[0];
}
else
{
return 0;
}
}
int main(void)
{
int i,* p;
SString s1,s2;
StrAssign(s1,"aaabaaaab");
printf("主串为：");
StrPrint(s1);
StrAssign(s2,"aaaab");
printf("子串为：");
StrPrint(s2);
p = (int *)malloc((StrLength(s2) + 1) * sizeof(int));
get_next(s2,p);
printf("子串的next的数组为：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
i = Index_KMP(s1,s2,1,p);
if (i)
{
printf("主串和子串在第%d个字符处首次匹配\n",i);
}
else
{
printf("主串和子串匹配不成功\n");
}
get_nextval(s2,p);
printf("子串的nextval数组为：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
printf("主串和子串在第%d个字符处首次匹配\n",Index_KMP(s1,s2,1,p));
printf("求串s1的从第5个字符起长度为5的子串s2:\n");
SubString(s2,s1,5,5);
printf("串s2为:");
StrPrint(s2);
return 0;
}
/*
在vc++6.0中的输出结果：
------------------------
主串为：a a a b a a a a b
子串为：a a a a b
子串的next的数组为：0 1 2 3 4
主串和子串在第5个字符处首次匹配
子串的nextval数组为：0 0 0 0 4
主串和子串在第5个字符处首次匹配
求串s1的从第5个字符起长度为5的子串s2:
串s2为:a a a a b
Press any key to continue
------------------------------
*/