急！！急！！急！！数据结构（C语言版）程序设计题： 使用KMP算法实现一个模式匹配。

#include cstring

银川网站制作公司哪家好，找创新互联公司！从网页设计、网站建设、微信开发、APP开发、自适应网站建设等网站项目制作，到程序开发，运营维护。创新互联公司公司2013年成立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联公司。

#include iostream

using namespace std;

//修正后的求next数组各值的函数代码

void get_nextval(char const* ptrn, int plen, int* nextval)

{

int i = 0; //i是从0开始的

nextval[i] = -1;

int j = -1;

while( i plen-1 )

{

if( j == -1 || ptrn[i] == ptrn[j] ) //循环的if部分

{

++i;

++j;

if( ptrn[i] != ptrn[j] ) //++i，++j之后，再次判断ptrn[i]与ptrn[j]的关系

nextval[i] = j;

else

nextval[i] = nextval[j];

}

else //循环的else部分

j = nextval[j];

}

}

void print_progress(char const* src, int src_index, char const* pstr, int pstr_index)

{

coutsrc_index"\t"srcendl;

coutpstr_index"\t";

for( int i = 0; i src_index-pstr_index; ++i )

cout" ";

coutpstrendl;

coutendl;

}

//int kmp_seach(char const*, int, char const*, int, int const*, int pos) KMP模式匹配函数

//输入：src, slen主串

//输入：patn, plen模式串

//输入：nextval KMP算法中的next函数值数组

int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)

{

int i = pos;

int j = 0;

while ( i slen j plen )

{

if( j == -1 || src[i] == patn[j] )

{

++i;

++j;

}

else

{

j = nextval[j];

//当匹配失败的时候直接用p[j_next]与s[i]比较，

//下面阐述怎么求这个值，即匹配失效后下一次匹配的位置

}

}

if( j = plen )

return i-plen;

else

return -1;

}

int main()

{

std::string src = "aabcabcebafabcabceabcaefabcacdabcab";

std::string prn = "abac";

int* nextval = new int[prn.size()];

//int* next = new int[prn.size()];

get_nextval(prn.data(), prn.size(), nextval);

//get_next(prn.data(), prn.size(), next);

for( int i = 0; i prn.size(); ++i )

coutnextval[i]"\t";

coutendl;

cout"result sub str: "src.substr( kmp_search(src.data(), src.size(), prn.data(), prn.size(), nextval, 0) )endl;

system("pause");

delete[] nextval;

return 0;

}

望楼主采纳！

C语言：我的字符串匹配函数

我这里运行，没有运行时错误，只是按你的代码结果不对。

调整后代码如下：

#include stdio.h

#include string.h

char *strstr(char*str1,char*str2)

{

int n1 = strlen(str1);

int n2 = strlen(str2);

int flg = 0;

char *p1 = str1;

char *p2 = str2;

if(n1n2) return NULL;

int i;

for(i=0;in1-n2+1;i++)

{

p1 = str1+i;

p2 = str2;

while(*p2!=NULL)//

{

if(*p1!=*p2) 

{

flg = 0;

p1++;

p2++;

break;

}

p1++;

p2++;

flg = 1;                

}

if(flg) return str1+i;//你到底要输出什么，原函数是输出位置int

}

return NULL;//

}

int main()

{

char str1[]="str1adsfqwer";

char str2[]="ads";

char *p = strstr(str1,str2);

printf("%s\n",p);

return 0;

}

C语言数据结构串的模式匹配算法问题

和while循环里面的一样，i指针退回原来的位置并指向下一位，应该是多少？i-j+2是吧！

这里不用指向下一位，直接return它的位置就行了，于是return

i-j+1

i-j+1和i-t[0]相等！

数据结构，C语言，模式匹配问题！！！急！！！ 求高手帮忙！谢啦！重赏！

修改如下 ：

//头文件定义为：

#include stdio.h

#include stdlib.h

#include string.h

//#include malloc.h

//宏定义：

#define OVERFLOW -2

#define OK 1

#define MAXSTRLEN 255

typedef char SString[MAXSTRLEN+1];

int strLengh(SString S)

{

int m;

for(m=1;S[m]!='\0';m++) ;

S[0]=m-1;;

return 0;

}

int Index(SString S,SString T,int pos)

{ //按照普通匹配查找方式查找模式串

int i=pos;

int j=1;

while(i=(int)S[0] j=(int)T[0])

{

if(S[i]==T[j])

{

++i;

++j;

}

else

{

i=i-j+2;

j=1;

}

}

if(jT[0])

return i-T[0];

else return 0;

}//Index

void get_next(SString T,int next[])

{ //求KMP算法中的next函数值，并存入数组next[]

int i=1;

next[1]=0;

int j=0;

while(i(int)T[0])

{

if(j==0 || T[i]==T[j])

{

++i;

++j;

next[i]=j;

}

else j=next[j];

}

}//next

int get_nextval(SString T,int nextval[])

{

int i=1;

nextval[1]=0;

int j=0;

while(i(int)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];

}

return 0;

}//nextval

int Index_KMP(SString S,SString T,int pos,int next[])

{ //KMP算法的实现过程

int i=pos;

int j=1,k=0;

while(i=(int)S[0] j=(int)T[0])

{

if(j==0 || S[i]==T[j])

{

++i;

++j;

}

else

{

j=next[j];

}

}

if(j(int)T[0])

return i-T[0];

else return 0;

}//Index_KMP

void main()

{

SString T,S;

char *p;

int pos;

int k1,k2,k;

int i,j;

int next[MAXSTRLEN];

int nextval[MAXSTRLEN];

printf("请输入字符串匹配主串：\n");

p=S[1];

gets(p);

printf("请输入字符串匹配模式串：\n");

p=T[1];

gets(p);

printf("您输入的字符串匹配中主串为：\n");

p=S[1];

puts(p);

printf("您输入的字符串匹配中模式串为：\n");

p=T[1];

puts(p);

printf("请您输入起始位置pos：");

scanf("%d",pos);

strLengh(S);

strLengh(T);

printf("\n----------运用普通算法------------\n");

printf("\n");

if(k1=Index(S,T,pos))

printf("匹配成功!\n普通匹配算法得模式串位置：%d\n",k1);

else

printf("没有找到，匹配失败!\n");

printf("\n----------运用KMP算法------------\n");

get_next(T,next);

printf("得到T的next[]序列为:");

for(i=1;i=T[0];i++)

printf("%d",next[i]);

get_nextval(T,nextval);

printf("\n得到T的nextval[]序列为:");

for(i=1;i=T[0];i++)

printf("%d",nextval[i]);

printf("\n");

if(k2=Index_KMP(S,T,pos,next))

printf("匹配成功!\nKMP算法得模式串位置：%d\n",k2);

else

printf("没有找到，匹配失败!");

}

《数据结构（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 (pos1 || posS[0] || len0 || lenS[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

------------------------------

*/

名称栏目：c语言模式匹配函数,c语言字符串匹配实现
文章源于：http://ybzwz.com/article/dsscosg.html