字符串与模式匹配算法

字符串与模式匹配算法作业讲评：链表应用举例

——Josephus问题

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

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

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

顺序表应用举例——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); /*删除出列的元素*/ }}算法复杂度分析（顺序结构）步骤：1:建立顺序表2:出列时间复杂度分析：出列元素的删除（移动实现）为基本运算（每次最多i-1个元素移动，需要n-1次）(n-1)+(n-2)+……+1=n(n-1)/2=>O(n2)算法复杂度分析（链表结构）步骤：(1)建立循环链表；(2)找循环单链表中的第s个结点放在指针变量p中(3)从p所指结点开始计数寻找第m个结点，输出该结点的元素值；(4)删除该结点，并将该结点的下一个结点放在指针变量p中，转去执行(2)，直到所有结点被删除为止；时间复杂度分析：三部分时间（创建链表：O(n)+求第s个结点：O(s)+求n个第m个应出列的元素：O(m*n))链表的用用：一元多项式和运算一元多项式：Pn(x)=p0+p1x+p2x2+…+pnxn线性表表示：P=(p0,p1,p2,…,pn)顺序表表示：只存系数（第i个元素存xi的系数）特殊问题：p(x)=1+2x10000+4x40000链表表示：每个结点结构系数指数0-110210000440000^一元多项式表示和运算-3数据定义： typedefstruct{floatc;//系数inte;//指数

structitem*next}Item;加法:相同指数对应结点的系数项相加，如和为0，删除结点，否则必定为和链表的一个结点。（实质上就是两个单链表的合并问题）32519011010112263两个一元多项式的乘法可以利用两个一元多项式相加的算法来实现M(x)=A(x)B(x)=A(x)[b1xe1+b2xe2+...+bnxen]=O(n2)复杂度的运算。字符串与模式匹配：字符串概念与抽象数据类型串模式匹配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*);串匹配函数：

char*strstr(constchar[],constchar[]);线性表到字符串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中第一次出现的位置。顺序结构字符串ADT的定义structSeqString{ /*顺序串的类型*/intMAXNUM; /*串允许的最大字符个数*/intn; /*串的长度，nMAXNUM*/char*c;};typedefstructSeqString*PSeqString;顺序串示例s=“abcdefg”abcdefgs.n=7s.c0123456MAXNUM-1字符串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;};链接结构字符串ADT的定义structStrNode; /*链串的结点*/ typedefstructStrNode*PStrNode;/*结点指针类型*/ structStrNode{ /*链串的结点结构*/ charc; PStrNodelink; }; typedefstructStrNode*LinkString; /*链串的类型*/字符串结尾？长度？字符串的链接存储示例sabcd^sabcd^不带头结点带头结点abcds带尾指针的循环链表链接存储字符串的基本运算创建空链串联结两个串取单链串的子串删除子串追加方式插入子串子串定位[模式匹配]求串长创建带头结点的空链串LinkStringcreateNullStr_link(void){ LinkStringpst; pst=(LinkString)malloc(sizeof(structStrNode)); if(pst!=NULL) pst->link=NULL; else printf("Outofspace!\n");/*创建失败*/ return(pst);}串模式匹配问题设有两个串t和p:t=t0t1…tn-1，p=p0p1…pm-1

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

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继续比较为止（匹配失败）。朴素的模式匹配——匹配子串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);朴素子串匹配法示例（每次p右移一个单元）

算法时间效率分析匹配失败的最坏情况：每趟匹配皆在最后一个字符不等，且有n-m+1趟匹配(每趟比较m个字符），共比较m*(n-m+1)次，由于m<<n，因此最坏时间复杂度O(n*m)。匹配失败的最好情况：n-m+1次比较[每趟只比较第一个字符]。匹配成功的最好情况：m次比较。匹配成功的最坏情况：与匹配失败的最坏情况相同。综上讨论：朴素模式匹配算法的时间复杂度为O(m*n)无回溯的模式匹配方法(KMP算法)利用已经匹配过子串的历史信息来指导下一步匹配的方案。模式串的特征数与特征向量模式串P开头的任意个字符，把它称为前缀子串。p0p1p2…pm-1在P的第i位置的左边，取出k个字符，称为i位置的左子串。pi-k+1...pi-2pi-1pi求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征数n[i]特征数组成的向量称为该模式串的特征向量。KMP算法基本思想第i个位置的特征值k仅依赖于模式p本身前i个字符的组成，而与目标t无关，一般可用next[i]表示与i对应的k值。若next[i]≥0，表示一旦匹配过程中pi与tj比较不等，可用p中以next[i]为下标的字符与tj进行比较。next[i]==-1?对于任意模式p，只要我们能够确定next[i](i=0,1,…,m-1)的值，就可以加速匹配过程，避免回溯问题。当tj≠pi时，模式串回溯（右移）i-next[i]个字符，从目标串tj位置继续下去。Next数组（特征向量）的计算在p与任意的目标串t匹配时，若发现tj≠pi，则意味着p0、p1、…、pi-1已经与t中对应的字符进行过比较，而且是相等的，否则轮不到tj与pi的比较，因此下面两个图是等价的