2023年7月20日发(作者：)

串的模式匹配问题实验总结

1实验题目：

实现Index(S,T,pos)函数。其中，Index(S,T,pos)为串T在串S的第pos个字符后第一次出现的位置。

2实验目的：

熟练掌握串模式匹配算法。

3实验方法：

分别用朴素模式匹配和KMP快速模式匹配来实现串的模式匹配问题。具体方法如下：

朴素模式匹配：输入两个字符串，主串S和子串T，从S串的第pos个位置开始与T的第一个位置比较，若不同执行 i=i-j+2；j=1两个语句；若相同，则执行语句 ++i; ++j;一直比较完毕为止，若S中有与T相同的部分则返回主串（S字符串）和子串（T字符串）相匹配时第一次出现的位置，若没有就返回0。

KMP快速模式匹配：构造函数get_next(char *T,int *next)，求出主串S串中各个字符的next值，然后在Index_KMP(char *S,char *T,int pos)函数中调用get_next(char *T,int *next)函数并调用next值，从S串的第pos 位置开始与T的第一个位置进行比较，若两者相等或j位置的字符next值等于0，则进行语句++i;++j;即一直向下进行。否则，执行语句 j=A[j]；直到比较完毕为止。若S中有与T相同的部分则返回主串（S字符串）和子串（T字符串）相匹配时第一次出现的位置，若没有就返回0

4实验过程与结果：

（1）、选择1功能“输入主串、子串和匹配起始位置”，输入主串S：asdfghjkl,

输入子串T：gh,输入pos的值为：2。

选择2功能 “朴素的模式匹配算法”，输出结果为 5；

选择3功能 “KMP快速模式匹配算法”，输出结果为 5；

选择0功能，退出程序。

截图如下：

（2）、选择1功能“输入主串、子串和匹配起始位置”，输入主串S：asdfghjkl,

输入子串T：wp, 输入pos的值为：2。

选择2功能 “朴素的模式匹配算法”，输出结果为 0；

选择3功能 “KMP快速模式匹配算法”，输出结果为 0；

选择1功能“输入主串、子串和匹配起始位置”，输入主串S：asdfghjkl,

输入子串T：sd, 输入pos的值为：4。

选择2功能 “朴素的模式匹配算法”，输出结果为 0；

选择3功能 “KMP快速模式匹配算法”，输出结果为 0；

选择0功能，退出程序。

截图如下：

5实验体会与收获：

（1） C语言中无法用string型直接定义字符串，所以要用char型的数组来实现字符串的定义。

（2） 在char S[]数组， 数组的首位即S[0]表示数组长度，用stolen()计算长度，输入的字符串逐步后移一位，此时S[1]存放第一个字符。

（3） 在主函数中，用get(S+1)；get(T+1);两个语句无法同时实现字符的输入，最后改用C++语句 cin>>S+1;

cin>>T+1;使字符的输入得到了实现。

（4） 程序用有必要的文字说明，以便运行时更加清晰明了。