字符串与模式匹配算法

字符串与模式匹配算法第1页，共42页，2023年，2月20日，星期六用数组来实现链表结构structNode{DataTypenum;intnext};structSlinklist{Nodelist[MAXNUM];intelementNum;}

1290-1634-1122第2页，共42页，2023年，2月20日，星期六3第3页，共42页，2023年，2月20日，星期六作业讲评：4第4页，共42页，2023年，2月20日，星期六5第5页，共42页，2023年，2月20日，星期六6第6页，共42页，2023年，2月20日，星期六7第7页，共42页，2023年，2月20日，星期六8第8页，共42页，2023年，2月20日，星期六9第9页，共42页，2023年，2月20日，星期六10第10页，共42页，2023年，2月20日，星期六11第11页，共42页，2023年，2月20日，星期六链表应用举例

——Josephus问题

求解Josephus问题的一般步骤为：

（1）首先利用线性表的一些运算如创建空线性表、插入元素等构造Josephus表；

（2）从Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第m个结点，重复此过程，直到Josephus表中的所有元素都删除。

12第12页，共42页，2023年，2月20日，星期六顺序表应用举例——Josephus问题voidjosephus_seq(PSeqListpalist,ints,intm){ints1,i,w;s1=s-1;for(i=palist->n;i>0;i--)/*找出列的元素*/{s1=(s1+m-1)%i;/*下一个出列的元素*/ w=palist->element[s1]; /*求下标为s1的元素的值*/printf(“Outelement%d\n”,w); /*元素出列*/ delete_seq(palist,s1); /*删除出列的元素*/ }}13第13页，共42页，2023年，2月20日，星期六算法复杂度分析（顺序结构）步骤：1:建立顺序表2:出列时间复杂度分析：出列元素的删除（移动实现）为基本运算（每次最多i-1个元素移动，需要n-1次）(n-1)+(n-2)+……+1=n(n-1)/2=>O(n2)14第14页，共42页，2023年，2月20日，星期六算法复杂度分析（链表结构）步骤：(1)建立循环链表；(2)找循环单链表中的第s个结点放在指针变量p中(3)从p所指结点开始计数寻找第m个结点，输出该结点的元素值；(4)删除该结点，并将该结点的下一个结点放在指针变量p中，转去执行(2)，直到所有结点被删除为止；时间复杂度分析：三部分时间（创建链表：O(n)+求第s个结点：O(s)+求n个第m个应出列的元素：O(m*n))15第15页，共42页，2023年，2月20日，星期六链表的用用：一元多项式和运算一元多项式：Pn(x)=p0+p1x+p2x2+…+pnxn线性表表示：P=(p0,p1,p2,…,pn)顺序表表示：只存系数（第i个元素存xi的系数）特殊问题：p(x)=1+2x10000+4x40000链表表示：每个结点结构系数指数0-110210000440000^16第16页，共42页，2023年，2月20日，星期六一元多项式表示和运算-3数据定义： typedefstruct{floatc;//系数inte;//指数

structitem*next}Item;加法:相同指数对应结点的系数项相加，如和为0，删除结点，否则必定为和链表的一个结点。（实质上就是两个单链表的合并问题）3251901101011226317第17页，共42页，2023年，2月20日，星期六两个一元多项式的乘法可以利用两个一元多项式相加的算法来实现M(x)=A(x)B(x)=A(x)[b1xe1+b2xe2+...+bnxen]=O(n2)复杂度的运算。18第18页，共42页，2023年，2月20日，星期六字符串与模式匹配：字符串概念与抽象数据类型串模式匹配19第19页，共42页，2023年，2月20日，星期六C语言中定义的字符串存储结构：字符指针…\0操作：<string.h>

char*strcpy(char*dst,char*sorc)intstrcmp(char*str1,char*str2);

char*strcat(char*dest,constchar*sorc,size);char*strstr(char*str,constchar*strSearch);size_tstrlen(constchar*str);gets(char*);puts(char*);20第20页，共42页，2023年，2月20日，星期六串匹配函数：

char*strstr(constchar[],constchar[]);21第21页，共42页，2023年，2月20日，星期六线性表到字符串ADTStringcreateNullStr(void)

创建一个空串。intIsNullStr(Strings)

判断串s是否为空串，若为空串，则返回1，否则返回0。intlength(Strings)

返回串s的长度。Stringconcat(Strings1,Stings2)

返回将串s1和s2拼接在一起构成的一个新串。StringsubStr(Strings,inti,intj)

在串s中，求从串的第i个字符开始连续j个字符所构成的子串。intindex(Strings1,Strings2)

如果串s2是s1的子串，则可求串s2在串s1中第一次出现的位置。22第22页，共42页，2023年，2月20日，星期六顺序结构字符串ADT的定义structSeqString{ /*顺序串的类型*/intMAXNUM; /*串允许的最大字符个数*/intn; /*串的长度，nMAXNUM*/char*c;};typedefstructSeqString*PSeqString;23第23页，共42页，2023年，2月20日，星期六顺序串示例s=“abcdefg”abcdefgs.n=7s.c0123456MAXNUM-124第24页，共42页，2023年，2月20日，星期六字符串ADT——创建顺序结构空串PSeqStringcreateNullStr_seq(intm){PSeqStringpstr=(PSeqString)malloc(sizeof(structSeqString)); if(pstr!=NULL){pstr->c=(char*)malloc(sizeof(char)*m);if(pstr->c！=NULL){pstr->n=0;pstr->MAXNUM=m;return(pstr)}elsefree(pstr);}printf("Outofspace!!\n");returnNULL;}structSeqString{ intMAXNUM;intn; char*c;};25第25页，共42页，2023年，2月20日，星期六链接结构字符串ADT的定义structStrNode; /*链串的结点*/ typedefstructStrNode*PStrNode;/*结点指针类型*/ structStrNode{ /*链串的结点结构*/ charc; PStrNodelink; }; typedefstructStrNode*LinkString; /*链串的类型*/字符串结尾？长度？26第26页，共42页，2023年，2月20日，星期六字符串的链接存储示例sabcd^sabcd^不带头结点带头结点abcds带尾指针的循环链表27第27页，共42页，2023年，2月20日，星期六链接存储字符串的基本运算创建空链串联结两个串取单链串的子串删除子串追加方式插入子串子串定位[模式匹配]求串长28第28页，共42页，2023年，2月20日，星期六创建带头结点的空链串LinkStringcreateNullStr_link(void){ LinkStringpst; pst=(LinkString)malloc(sizeof(structStrNode)); if(pst!=NULL) pst->link=NULL; else printf("Outofspace!\n");/*创建失败*/ return(pst);}29第29页，共42页，2023年，2月20日，星期六串模式匹配问题设有两个串t和p:t=t0t1…tn-1，p=p0p1…pm-1

其中1<m<=n(通常m<<n)模式匹配的目的是在t中找出和p相同的子串。此时，t称为“目标”，而p称为“模式”。模式匹配的结果有两种：匹配成功：t中存在等于p的子串，返回子串在t中的位置匹配失败：返回一个特定的标志（如-1）。30第30页，共42页，2023年，2月20日，星期六两种模式匹配方法模式匹配是一个比较复杂的字符串操作，下面的讨论是基于字符串的顺序存储结构进行。分为朴素的模式匹配方法和无回溯的模式匹配方法匹配思想匹配示例匹配算法算法时间效率分析31第31页，共42页，2023年，2月20日，星期六朴素的模式匹配思想

p中字符依次与t中字符一一比较：

t0t1…tjtj+1…tj+m-1…tn

p0p1…pm-1

如果对于所有的i(0<=i<=m-1),皆有tj+i=pi，则匹配成功，返回位置j；否则，此趟匹配失败，这时将p右移一个字符，进行下一趟匹配：

t0t1…tjtj+1tj+2…tj+m…tn

p0p1…pm-1

直到匹配成功或p移动到无法与t继续比较为止（匹配失败）。32第32页，共42页，2023年，2月20日，星期六朴素的模式匹配——匹配子串intindex(PSeqStringt,PSeqStringp)求p所指的串在t所指的串中第一次出现时，p所指串的第一个元素在t所指的串中的序号(下标+1)。

算法：用p中的字符依次与t中的字符比较，如果：t0=p0，t1=p1，…，tm-1=pm-1，则匹配成功，返回字符t0的位置。否则：t0++;从p0开始新一轮比较。直到：匹配成功。或：strlen(p)>strlen(t0);33第33页，共42页，2023年，2月20日，星期六朴素子串匹配法示例（每次p右移一个单元）

下标j01234567891011121314151617目标taabcbabcaabcaababc模式pabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababc34第34页，共42页，2023年，2月20日，星期六35第35页，共42页，2023年，2月20日，星期六算法时间效率分析匹配失败的最坏情况：每趟匹配皆在最后一个字符不等，且有n-m+1趟匹配(每趟比较m个字符），共比较m*(n-m+1)次，由于m<<n，因此最坏时间复杂度O(n*m)。匹配失败的最好情况：n-m+1次比较[每趟只比较第一个字符]。匹配成功的最好情况：m次比较。匹配成功的最坏情况：与匹配失败的最坏情况相同。综上讨论：朴素模式匹配算法的时间复杂度为O(m*n)36第36页，共42页，2023年，2月20日，星期六无回溯的模式匹配方法(KMP算法)利用已经匹配过子串的历史信息来指导下一步匹配的方案。37第37页，共42页，2023年，2月20日，星期六模式串的特征数与特征向量模式串P开头的任意个字符，把它称为前缀子串。p0p1p2…pm-1在P的第i位置的左边，取出k个字符，称为i位置的左子串。pi-k+1...pi-2pi-1pi求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征数n[i]特征数组成的向量称为该模式串的特征向量。38第38页，共42页，2023年，2月20日，星期六KMP算法基本思想第i个位置的特征值k仅依赖于模式p本身前i个字符的组成，