字符串与模式匹配算法幻灯片.ppt

《字符串与模式匹配算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《字符串与模式匹配算法幻灯片.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、字符串与模式匹配算字符串与模式匹配算法法第1页，共42页，编辑于2022年，星期五用数组来实现链表结构用数组来实现链表结构structNodeDataTypenum;intnext;structSlinklistNodelistMAXNUM;intelementNum;1290-1634-1122第2页，共42页，编辑于2022年，星期五3第3页，共42页，编辑于2022年，星期五作业讲评：作业讲评：4第4页，共42页，编辑于2022年，星期五5第5页，共42页，编辑于2022年，星期五6第6页，共42页，编辑于2022年，星期五7第7页，共42页，编辑于2022年，星期五8第8页，共42页，

2、编辑于2022年，星期五9第9页，共42页，编辑于2022年，星期五10第10页，共42页，编辑于2022年，星期五11第11页，共42页，编辑于2022年，星期五链表应用举例链表应用举例 Josephus问题问题求解Josephus问题的一般步骤为：（1）首先利用线性表的一些运算如创建空线性表、插入元素等构造Josephus表；（2）从Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第m个结点，重复此过程，直到Josephus表中的所有元素都删除。12第12页，共42页，编辑于2022年，星期五顺序表应用举例顺序表应用

3、举例 Josephus问题问题voidjosephus_seq(PSeqListpalist,ints,intm)ints1,i,w;s1=s-1;for(i=palist-n;i0;i-)/*找出列的元素*/s1=(s1+m-1)%i;/*下一个出列的元素*/w=palist-elements1;/*求下标为s1的元素的值*/printf(“Outelement%dn”,w);/*元素出列*/delete_seq(palist,s1);/*删除出列的元素*/13第13页，共42页，编辑于2022年，星期五算法复杂度分析算法复杂度分析 （顺序结构）（顺序结构）步骤：1:建立顺序表2:出列时间复

4、杂度分析：出列元素的删除（移动实现）为基本运算（每次最多i-1个元素移动，需要n-1次）(n-1)+(n-2)+1=n(n-1)/2=O(n2)14第14页，共42页，编辑于2022年，星期五算法复杂度分析算法复杂度分析 （链表结构）（链表结构）步骤：(1)建立循环链表；(2)找循环单链表中的第s个结点放在指针变量p中(3)从p所指结点开始计数寻找第m个结点，输出该结点的元素值；(4)删除该结点，并将该结点的下一个结点放在指针变量p中，转去执行(2)，直到所有结点被删除为止；时间复杂度分析：三部分时间（创建链表：O(n)+求第s个结点：O(s)+求n个第m个应出列的元素：O(m*n)15第15

5、页，共42页，编辑于2022年，星期五链表的用用：一元多项式和运算链表的用用：一元多项式和运算一元多项式：一元多项式：P Pn n(x)=p(x)=p0 0+p+p1 1x+px+p2 2x x2 2+p+pn n x xn n线性表表示：线性表表示：P=(pP=(p0 0,p,p1 1,p,p2 2,p,pn n)顺序表表示：顺序表表示：只存系数（第只存系数（第i i个元素存个元素存x xi i的系数）的系数）特殊问题：特殊问题：p(x)=1+2xp(x)=1+2x10000 10000+4x+4x4000040000链表表示：链表表示：每个结点结构每个结点结构系数指数0-110210000

6、44000016第16页，共42页，编辑于2022年，星期五一元多项式表示和运算一元多项式表示和运算-3数据定义：typedef struct float c;/系数 int e;/指数 struct item*next Item;加法:相同指数对应结点的系数项相加，如和为0，删除结点，否则必定为 和链表的一个结点。（实质上就是两个单链表的合并问题）3251901101011226317第17页，共42页，编辑于2022年，星期五两个一元多项式的乘法两个一元多项式的乘法可以利用两个一元多项式相加的算法来实现M(x)=A(x)B(x)=A(x)b1xe1+b2xe2+.+bnxen=O(n2)复

7、杂度的运算。18第18页，共42页，编辑于2022年，星期五字符串与模式匹配：字符串与模式匹配：字符串概念与抽象数据类型串模式匹配19第19页，共42页，编辑于2022年，星期五C语言中定义的字符串语言中定义的字符串存储结构：字符指针0操作：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

8、(char*);puts(char*);20第20页，共42页，编辑于2022年，星期五串匹配函数：串匹配函数：char*strstr(const char,constchar);21第21页，共42页，编辑于2022年，星期五线性表到字符串线性表到字符串ADTString createNullStr(void)创建一个空串。int IsNullStr(String s)判断串s是否为空串，若为空串，则返回1，否则返回0。int length(String s)返回串s的长度。String concat(String s1,Sting s2)返回将串s1和s2拼接在一起构成的一个新串。Stri

9、ng subStr(String s,int i,int j)在串s中，求从串的第i个字符开始连续j个字符所构成的子串。int index(String s1,String s2)如果串s2是s1的子串，则可求串s2在串s1中第一次出现的位置。22第22页，共42页，编辑于2022年，星期五顺序结构字符串顺序结构字符串ADT的定义的定义struct SeqString/*顺序串的类型*/int MAXNUM;/*串允许的最大字符个数*/int n;/*串的长度，nMAXNUM*/char *c;typedef struct SeqString *PSeqString;23第23页，共42页，编

10、辑于2022年，星期五顺序串示例顺序串示例s=“abcdefg”abc defgs.n=7s.c 0 1 2 3 4 5 6 MAXNUM-124第24页，共42页，编辑于2022年，星期五字符串字符串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=

11、m;return(pstr)elsefree(pstr);printf(Outofspace!n);returnNULL;struct SeqString int MAXNUM;int n;char *c;25第25页，共42页，编辑于2022年，星期五链接结构字符串链接结构字符串ADT的定义的定义structStrNode;/*链串的结点*/typedefstructStrNode*PStrNode;/*结点指针类型*/structStrNode/*链串的结点结构*/charc;PStrNodelink;typedefstructStrNode*LinkString;/*链串的类型*/字符串

12、结尾？长度？26第26页，共42页，编辑于2022年，星期五字符串的链接存储示例字符串的链接存储示例sabcdsabcd不带头结点不带头结点带头结点带头结点abcds带尾指针的循环链表带尾指针的循环链表27第27页，共42页，编辑于2022年，星期五链接存储字符串的基本运算链接存储字符串的基本运算创建空链串联结两个串取单链串的子串取单链串的子串删除子串追加方式插入子串追加方式插入子串子串定位模式匹配求串长28第28页，共42页，编辑于2022年，星期五创建带头结点的空链串创建带头结点的空链串LinkStringcreateNullStr_link(void)LinkStringpst;pst=

13、(LinkString)malloc(sizeof(structStrNode);if(pst!=NULL)pst-link=NULL;elseprintf(Outofspace!n);/*创建失败*/return(pst);29第29页，共42页，编辑于2022年，星期五串模式匹配问题串模式匹配问题设有两个串t和p:t=t0t1tn-1，p=p0p1pm-1其中1m=n(通常mn)模式匹配的目的是在t中找出和p相同的子串。此时，t称为“目标”，而p称为“模式”。模式匹配的结果有两种：匹配成功：t中存在等于p的子串，返回子串在t中的位置匹配失败：返回一个特定的标志（如-1）。30第30页，共4

14、2页，编辑于2022年，星期五两种模式匹配方法两种模式匹配方法模式匹配是一个比较复杂的字符串操作，下面的讨论是基于字符串的顺序存储顺序存储结构进行。分为朴素的模式匹配方法和无回溯的模式匹配方法匹配思想匹配示例匹配算法算法时间效率分析31第31页，共42页，编辑于2022年，星期五朴素的模式匹配思想朴素的模式匹配思想p p中字符依次与中字符依次与t t中字符一一比较：中字符一一比较：t t0 0 t t1 1 t tj j t tj+1j+1 t tj+m-1j+m-1 t tn n p p0 0 p p1 1 p pm-1m-1 如果对于所有的如果对于所有的i i(0=i=m-1)(0=ist

15、rlen(t0);33第33页，共42页，编辑于2022年，星期五朴素子串匹配法示例（朴素子串匹配法示例（每次每次p右移一个单元）右移一个单元）下标j01234567891011121314151617目标taabcbabcaabcaababc模式pabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababc34第34页，共42页，编辑于2022年，星期五35第35页，共42页，编辑于2022年，星期五算法时间效率分析算法时间效率分析匹配失败的最坏情况：每趟匹配皆在最后一个字

16、符不等，且有n-m+1趟匹配(每趟比较m个字符），共比较m*(n-m+1)次，由于mn，因此最坏时间复杂度O(n*m)。匹配失败的最好情况：n-m+1次比较每趟只比较第一个字符。匹配成功的最好情况：m次比较。匹配成功的最坏情况：与匹配失败的最坏情况相同。综上讨论：朴素模式匹配算法的时间复杂度为O(m*n)36第36页，共42页，编辑于2022年，星期五无回溯的模式匹配方法无回溯的模式匹配方法(KMP算法算法)利用已经匹配过子串的历史信息来指导下一步匹配的方案。37第37页，共42页，编辑于2022年，星期五模式串的特征数与特征向量模式串的特征数与特征向量模式串P开头的任意个字符，把它称为前缀子

17、串。p0p1p2pm-1在P的第i位置的左边，取出k个字符，称为i位置的左子串。pi-k+1.pi-2 pi-1 pi求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征数特征数ni特征数组成的向量称为该模式串的特征向量特征向量。38第38页，共42页，编辑于2022年，星期五KMP算法基本思想算法基本思想第i个位置的特征值k仅依赖于模式p本身前i个字符的组成，而与目标t无关，一般可用nexti表示与i对应的k值。若nexti0，表示一旦匹配过程中pi与tj比较不等，可用p中以nexti为下标的字符与tj进行比较。n

18、exti=-1?对于任意模式p，只要我们能够确定nexti(i=0,1,m-1)的值，就可以加速匹配过程，避免回溯问题。当tjpi时，模式串回溯（右移）i-nexti个字符，从目标串tj位置继续下去。39第39页，共42页，编辑于2022年，星期五Next数组（特征向量）的计算数组（特征向量）的计算在p与任意的目标串t匹配时，若发现tjpi，则意味着p0、p1、pi-1已经与t中对应的字符进行过比较，而且是相等的，否则轮不到tj与pi的比较，因此下面两个图是等价的。t0tj-i tj-i+1 tj-1 tj p0 pi-1 pit0tj-i-1 p0 pi-1 tj p0 pi-1 pi40第40页，共42页，编辑于2022年，星期五然后把然后把p右移若干位，右移若干位，tj以前的比较工作相当于用以前的比较工作相当于用p0pi-1的一个前的一个前缀与它的一个长度相同的后缀进行比较，显然比较的结果由缀与它的一个长度相同的后缀进行比较，显然比较的结果由p本本身决定。身决定。t0 tj-i-1 p0pi-k pi-1 tjp0 pk-1 pk?前缀前缀后缀后缀41第41页，共42页，编辑于2022年，星期五作业：上机一起布置。42第42页，共42页，编辑于2022年，星期五