串的模式匹配(共4页).doc

实验四 顺序串的各种模式匹配一、 实验目的熟悉串的有关概念，掌握串的存储结构及串的模式匹配算法。二、实验内容由用户随意输入两个串：主串S和模式串T，设S=s1s2sn，T=t1t2tm，且0m=n。 1（必做）、用简单模式匹配算法判断模式串T是否在主串S中，若在，则输出模式串在主串的第一匹配位置，否则，匹配失败，返回零值。 2（选做）、用KMP模式匹配算法判断模式串T是否在主串S中，若在，则输出模式串在主串的第一匹配位置，否则，匹配失败，返回零值。三、算法思想与算法描述单链表是线性表的链式存储结构的一种形式，它用一组地址任意的存储单元存放线性表的各个元素。四、实验步骤与算法实现#include#includeusing namespace std;typedef struct taglinint data;taglin* next;lin;void initlin(lin* &L,int e)lin* p=L,* s;whil