正文
c语言模式匹配函数,c语言字符串匹配实现
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
急！！急！！急！！数据结构（C语言版）程序设计题： 使用KMP算法实现一个模式匹配。
#include cstring
#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
------------------------------
*/
