串的匹配
实验4-1 串的匹配
1、实验目的
了解串的特点，描述方法及有关概念，掌握串的模式匹配算法。
2、实验内容
已知主串为"aaabaaaab"，子串为"aaaab"，求模式串的next值和nextval值，实现模式串的匹配算法。
3、实验要点及说明
模式匹配：子串的定位操作通常称为串的模式匹配。它是各种串处理系统中最重要的操作之一。
模式匹配的算法基本思想是：从主串S的第pos 个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为零。
改进的模式匹配算法：每一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能的一段距离后，继续进行比较。
在改进的模式匹配算法(KMP算法)中，当匹配过程中产生“失配”时，指针i不变，指针j退回到next[j]所指示的位置上重新进行比较，并且当指针j退至零时，指针i和指针j需同时增1。即若主串的第i个字符和模式的第1个字符不等，应从主串的第i+1字符重新进行匹配。
4、参考程序
#include
#include
#include
#include
#define MAX_STR_LEN 40 /* 用户可在255(1个字节)以内定义最大串长 */
typedef char SString[MAX_STR_LEN+1]; /* 0号单元存放串的长度 */
void StrAssign(SString T,char *chars)
{ /* 生成一个其值等于chars的串T */
int i;
if(strlen(chars)>MAX_STR_LEN)
exit(0);
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
}
}
int StrLength(SString S)
{ /* 返回串S的元素个数 */
return S[0];
}
void get_next(SString T,int next[])
{ /* 求模式串T的next函数值并存入数组next。算法4.7 */
int i=1,j=0;
next[1]=0;
while(i if(j==0||T[i]==T[j]) { ++i; ++j; next[i]=j; } else j=next[j]; } void get_nextval(SString T,int nextval[]) { /* 求模式串T的next函数修正值并存入数组nextval。算法4.8 */ int i=1,j=0; nextval[1]=0; while(i 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]; } int Index_KMP(SString S,SString T,int pos,int next[]) { /* 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。 */ /* 其中，T非空，1≤pos≤StrLength(S)。算法4.6 */ 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; } void StrPrint(SString T) { /* 输出字符串T。另加 */ int i; for(i=1;i<=T[0];i++) printf("%c",T[i]); printf("\n"); } void main() { int i,*p; SString s1,s2; /* 以教科书算法4.8之上的数据为例 */ StrAssign(s1,"aaabaaaab"); printf("主串为: "); StrPrint(s1); StrAssign(s2,"aaaab"); printf("子串为: "); StrPrint(s2); p=(int*)malloc((StrLength(s2)+1)*sizeof(int)); /* 生成s2的next数组空间 */ get_next(s2,p); /* 利用算法4.7，求得next数组，存于p中 */ printf("子串的next数组为: "); for(i=1;i<=StrLength(s2);i++) printf("%d ",*(p+i)); printf("\n"); i=Index_KMP(s1,s2,1,p); /* 利用算法4.6求得串s2在s1中首次匹配的位置i */ if(i) printf("主串和子串在第%d个字符处首次匹配\n",i); else printf("主串和子串匹配不成功\n"); get_nextval(s2,p); /* 利用算法4.8，求得next数组，存于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)); }