数据结构--串的应用,模式匹配算法附源程序(转).doc
文本预览下载声明
这一篇写的模式匹配算法是以上一篇串的基本操作为基础的，这里面写了模式匹配的三种不同的算法，其实每个算法都是前一算法的改进，有简单匹配，头尾匹配，还有改进后KMP算法 这是文件fun.h:
#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(pos0||poss-length)??exit(OVERFLOW);
i=pos-1;
j=0;
while(is-length jsub-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(is-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(jsub-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(is-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(pos1||poss-length)
? ?? ?? ? exit(OVERFLOW);
i=pos-1;
j=0;
while(is-length jT-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
复制代码
这是mian函数：
#include mystring.h
#include fun.h
int main()
{
String str1,str2,str3;
i
显示全部