数据结构：串c讲解3.pptVIP

例题 1．下面关于串的的叙述中，哪一个是不正确的？（ ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 例题 1、若串S=‘abcde’,其子串的数目是（ ） 2．若串S=‘bioinformatics’,其子串的数目是（ ） 空串是任意串的子串； 任意串是其自身的子串。 4.1串类型的定义 (9)strlen size_t strlen(const char *str); 返回字符串str的长度，‘\0’不算在内。 (10)memcpy void *memcpy(void *to, const void *from, size_t count); 把from中的count个字符拷贝到to中。并返回to。 4.1串类型的定义 (11)memcmp int memcmp(const void *buf1, const void *buf2, size_t count); 比较buf1和buf2的前count个字符，返回值与strcmp的返回值相同。 (12)memset void *memset(void *buf, int ch, size_t count); 把buf中的前count个字符替换为ch，并返回buf。 哪个是今天要讨论的模式匹配 the The quick brown fox jumps over the lazy dog jay The quick brown fox jumps over the lazy dog 复习一下穷举的模式匹配算法 ababcabcacbab 主串 abcac 模式串 1.穷举模式匹配算法复杂度 目标串：00000000000000000000000001（25个0） 模式串：0001 （3个0） The naive string-matching algorithm ababcabcacbab 主串 abcac 模式串 再次复习一下穷举的模式匹配算法 KMP算法的基本思想(一) 我们要解决的问题是:当“失配”(si?pj)时,模式串P“向右滑动”的可行距离有多远;或者说,下一步si应该与模式串中的哪个字符比较? 可以推断:答案将完全取决于模式串,而与主串无关 KMP算法的基本思想(一) 因此,可以预先为模式串设定一个数组next[j],当“失配”(si?pj)时,i不变,j改为next[j] 2.KMP快速模式匹配 主串：‘s1，s2……sn’ 模式串：‘p1，p2……pm’ 若si?pj，假设下一步主串中第i个字符应与模式中第k（kj）个字符继续比较，则模式中前k-1个字符的子串必须满足下列关系式，且不存在k’k满足下列关系式。 ‘p1，p2……pk-1’= ‘si-k+1，si-k+2……si-1’ 而已经得到的“部分匹配”（即上一趟的比较）为： ‘pj-k+1，pj-k+2……pj-1’= ‘si-k+1，si-k+2……si-1’ 2.KMP快速模式匹配 下一步si应该与模式串中的哪个字符比较? 答案将完全取决于模式串,而与主串无关 在匹配过程中， 当si?pj时，若模式串中存在满足以上式子的两个字串，仅需将模式向右滑动至模式中第k个字符和主串中第i个字符对齐。 令next[j]=k KMP算法的基本思想(二) 一般情况下, 模式串的next函数的定义如下: 0 当j=1时 next[j]= max{k|1kj且“p1...pk-1”=“pj-k+1...pj-1”} 1 其他情况 如: 现有模式串abcac,求其next值 现有模式串abaabcac,求其next值 现有模式串abaabacaca,求其next值 求next数组 如何求得next[j]的值？ P82-83 此函数值仅取决于模式串本身而和相匹配的主串无关。 next[1]=0 设 next[j]=k，这表明在模式串中存在下列关系： 求next数组 此时next[j+1]=？ 有两种情况： 1、pk=pj，则 求next数组 ‘p1，p2…pk-1，pk…pj-k+1，pj-k+2…pj-1pj…… pm’ 现有模式串abaabacaca,求其next值 更多模式匹配算法 Boyer-Moore算法 这个算法KMP算法的不同点是在作s[k+1..k+m]与t[1..m]的匹配测试时是