数据结构--串的应用，模式匹配算法（从简单算法到改进的KMP算法）
这一篇写的模式匹配算法是以上一篇串的基本操作为基础的，这里面写了模式匹配的三种不同的算法，其实每个算法都是前一算法的改进，有简单匹配，头尾匹配，还有改进后KMP算法这是文件fun.h:[code]#ifndef FUN_H
#define FUN_H
#include "mystring.h"
int Index(String *sub,String *s,int pos); //匹配的简单算法：返回子串sub在主串s中的位置，失败则返回0
int Index_HeadToTail(String *sub,String *s,int pos);//匹配的改进算法：头尾同时进行比较
void get_next(String *,int []); //KMP算法中的next函数算法
int kmp(String *s,String *T,int [],int pos); //KMP的改进算法
int Index(String *sub,String *s,int pos)
{
int i,j;
if(pos<0||pos>s->length) exit(OVERFLOW);
i=pos-1;
j=0;
while(i<s->length && j<sub->length)
{
if(s->ch[i]==sub->ch[j])
{
++i;++j;
}
else
{
i=i-j+2;
j=0;
}
}
if(j==sub->length)
{
printf("Success!");
TURNLINE;
return i-sub->length;//匹配成功，并且此时i,j的位置都在'\0'上，则返回在主串中匹配的第一个位置
}
else
{
printf("Failed!");
TURNLINE;
return 0;
}
}
int Index_HeadToTail(String *sub,String *s,int pos)
{
int i,j=1,k=1;
i=pos-1;
while(i<s->length)
{
if(s->ch[i]!=sub->ch[0]) ++i; //如果头字符匹配不成功则继续匹配下一个
else if (s->ch[i+sub->length-1]!=sub->ch[sub->length-1]) ++i; //如果头字符匹配成功，但尾字符匹配不成功，继续匹配下一个
else
{
while(j<sub->length && s->ch[i+k]==sub->ch[j])
{
++k;++j;
}
if(j==sub->length)
{
printf("Success!");
TURNLINE;
return i;
}
else
{
printf("Failed");
TURNLINE;
return 0;
}
}
}
return 0;
}
void get_next(String *s,int next[])
{
int i,j;
next[0]=-1;
i=0;
j=-1;
while(i<s->length)
{
if(j==-1||s->ch[i]==s->ch[j])
{
++i;
++j;
if(s->ch[i]!=s->ch[j]) next[i]=j;
else next[i]=next[j];
}
else j=next[j];
}
}
int kmp(String *s,String *T,int next[],int pos)
{
int i,j;
if(pos<1||pos>s->length)
exit(OVERFLOW);
i=pos-1;
j=0;
while(i<s->length && j<T->length)
{
if(s->ch[i]==T->ch[j] || j==-1)
{
++i;
++j;
}
else j=next[j];
}
if(j==T->length)
{
printf("Success!");
TURNLINE;
return i-T->length;
}
else
{
printf("Failed!");
TURNLINE;
return 0;
}
}
#endif[/code]这是mian函数：[code]#include "mystring.h"
#include "fun.h"
int main()
{
String str1,str2,str3;
int index,next[10];
int i;
char *chars="aaaababaabcacaabc\0";
char *chars1="ababa\0";
strAssign(&str1,chars);
/*strCopy(&str1,&str2);*/
strAssign(&str2,chars1);
get_next(&str2,next);
strPrint(&str1);
strPrint(&str2);
for(i=0;i<5;++i)
printf("%3d",next[i]);TURNLINE;
index=kmp(&str1,&str2,next,1);
printf("%d\n",index);
return 0;
}[/code]
页:
[1]