搜索
第4章特殊的线性表——串问题的提出查毒程序搜索引擎1.串的逻辑结构串：由零个或多个任意字符组成的有限序列。串长度：串中所包含的字符个数。空串：长度为0的串，记为：。非空串通常记为：S=“a1a2…an”其中：S是串名，双引号是定界符，双引号引起来的部分是串值，ai（1≤i≤n）是一个任意字符。1.串的逻辑结构两个串相等：如果两个串的长度相等且对应字符都相等。子串：串中任意连续的字符组成的子序列称为该串。主串：包含子串的串。子串的第一个字符在主串中的序号称为子串的位置。顺序串：用数组来存储串中的字符序列。（1）用一个变量来表示串的长度。2.串的存储结构——顺序串如何表示串的长度？顺序串：用数组来存储串中的字符序列。（2）在串尾存储一个不会在串中出现的特殊字符作为串的终结符。2.串的存储结构——顺序串如何表示串的长度？顺序串：用数组来存储串中的字符序列。（3）用数组的0号单元存放串的长度，串值从1号单元开始存放。2.串的存储结构——顺序串如何表示串的长度？链接串：用链接存储结构来存储串。p552.串的存储结构——链接串3.串的基本操作串的链接串的比较串的复制习题4.4、4.5、4.6习题4.7。编写一个函数来颠倒单词在字符串里的出现顺序。【《程序员面试攻略(第2版)》p81】例如，把字符串“Doordonot,thereisnotry.”转换为“try.noistherenot,doorDo”。假设所有单词都以空格为分隔符，标点符号也当做字母来对待。请对你的设计思路做出解释，并对你的解决方案的执行效率进行评估。3.串的基本操作删除特定字符。【《程序员面试攻略(第2版)》p78】用C语言编写一个高效率的函数来删除字符串里的给定字符。这个函数的调用模型如下所示：voidRemoveChars(charstr[],charremove[]);注意，remove中的所有字符都必须从str中删除干净。比如说，如果str是“BattleoftheVowels:HawaiiVS.Grozny”，remove是“aeiou”，这个函数将把str转换为“BttlfthVwls:Hwvs.Grzny”。请对你的设计思路做出解释，并对你解决方案的执行效率进行评估。4.串的应用——模式匹配模式匹配：给定主串S=s1s2…sn和模式T=t1t2…tm，在S中寻找T的过程称为模式匹配。如果匹配成功，返回T在S中的位置，如果匹配失败，返回0。4.串的应用——BF模式匹配算法基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，直到T中的字符全部比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。例：主串S=ababcabcacbab，模式T=abcacababcabcacbabi=3，j=3失败；i回溯到2，j回溯到1ijijij第1趟abcac4.串的应用——BF模式匹配算法ababcabcacbabi=3，j=3失败；i回溯到2，j回溯到1ji第1趟abcac例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法ababcabcacbabi=2，j=1失败i回溯到3，j回溯到1第2趟ijabcac例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法ababcabcacbabi=2，j=1失败i回溯到3，j回溯到1第2趟ijabcac例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法ababcabcacbababcaci=7，j=5失败i回溯到4，j回溯到1第3趟ijijijijij例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法ababcabcacbababcaci=7，j=5失败i回溯到4，j回溯到1第3趟ij例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法ababcabcacbababcaci=4，j=1失败i回溯到5，j回溯到1第4趟ij例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法ababcabcacbababcaci=4，j=1失败i回溯到5，j回溯到1第4趟ij例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法ababcabcacbababcaci=5，j=1失败i回溯到6，j回溯到1第5趟ij例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法ababcabcacbababcaci=5，j=1失败i回溯到6，j回溯到1第5趟ij例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法ababcabcacbababcaci=11，j=6，T中全部字符都比较完毕，匹配成功。第6趟ijijijijij例：主串S=ababcabcacbab，模式T=abcac4.串的应用——BF模式匹配算法1.在串S和串T中设比较的起始下标i和j；2.循环直到S或T的所有字符均比较完；2.1如果S[i]=T[j]，继续比较S和T的下一个字符；2.2否则，将i和j回溯，准备下一趟比较；3.如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回0；4.串的应用——BF模式匹配算法intBFmatching(chars[],chart[]){i=1;j=1;while(i=s[0]&&j=t[0]){if(s[i]==t[j]){i++;j++;}else{i=i-j+2;j=1;}}if(jt[0])return(i-j+1);elsereturn0;}4.串的应用——BF模式匹配算法4.串的应用——BF模式匹配算法设串s长度为n，串t长度为m，在匹配成功的情况下，考虑两种极端情况：最好情况：不成功的匹配都发生在串t的第一个字符。例如：s=aaaaabcdt=bcd设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能情况共有n-m+1种，则：设从si开始与t串匹配成功的概率为pi，在等概率情况下pi=1/(nm+1)，平均比较的次数是因此最好情况下的时间复杂度是O(n+m)。4.串的应用——BF模式匹配算法设串s长度为n，串t长度为m，在匹配成功的情况下，考虑两种极端情况：最坏情况：不成功的匹配都发生在串t的最后一个字符。例如：s=aaaaabt=aaab“设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此平均比较的次数是一般情况下，mn，因此最坏情况下的时间复杂度是O(nm)。4.串的应用——BF模式匹配算法为什么BF算法时间性能低？在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。如何在匹配不成功时主串不回溯？主串不回溯，模式就需要向右滑动一段距离。如何确定模式的滑动距离？i=3，j=3失败；s2=t2;t1≠t2∴t1≠s2ababcabcacbabij第1趟abcacababcabcacbab第2趟abcac4.串的应用——KMP模式匹配算法i=3，j=3失败；s2=t2;t1≠t2∴t1≠s2ababcabcacbabij第1趟abcacababcabcacbababcac第3趟4.串的应用——KMP模式匹配算法ababcabcacbababcac第3趟iji=7，j=5失败s4=t2;t1≠t2∴t1≠s4ababcabcacbababcac第4趟4.串的应用——KMP模式匹配算法ababcabcacbababcac第3趟iji=7，j=5失败s5=t3;t1≠t3∴t1≠s5ababcabcacbababcac第5趟4.串的应用——KMP模式匹配算法ababcabcacbababcac第3趟iji=7，j=5失败s5=t3;t1≠t3∴t1≠s5ababcabcacbababcac第6趟匹配成功4.串的应用——KMP模式匹配算法4.串的应用——KMP模式匹配算法结论：i可以不回溯，模式向右滑动到的新比较起点k，并且k仅与模式串T有关！需要讨论两个问题：①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？②模式应该向右滑多远才是最高效率的?请抓住部分匹配时的两个特征：（1）设模式滑动到第k个字符，则T1～Tk-1＝Si-(k-1)～Si-1S=ababcabcacbabT=abcacikjS=ababcabcacbabT=abcacik4.串的应用——KMP模式匹配算法请抓住部分匹配时的两个特征：两式联立可得：T1～Tk-1＝Tj-(k-1)～Tj-1（2）则Tj-(k-1)～Tj-1＝Si-(k-1)～Si-1S=ababcabcacbabT=abcacikjiS=ababcabcacbabT=abcacjk（1）设模式滑动到第k个字符，则T1～Tk-1＝Si-(k-1)～Si-14.串的应用——KMP模式匹配算法T1…Tk-1＝Tj-(k-1)…Tj-1说明了什么？（1）k与j具有函数关系，由当前失配位置j，可以计算出滑动位置k（即比较的新起点）；（2）滑动位置k仅与模式串T有关。从第1位往右经过k-1位从j-1位往左经过k-1位k＝max{k|1kj且T1…Tk-1＝Tj-(k-1)…Tj-1}T1…Tk-1＝Tj-(k-1)…Tj-1的物理意义是什么？模式应该向右滑多远才是最高效率的?4.串的应用——KMP模式匹配算法next[j]＝0当j＝1时//不比较max{k|1kj且T1…Tk-1=Tj-(k-1)…Tj-1}1其他情况令k=next[j]，则：next[j]函数表征着模式T中最大相同首子串和尾子串（真子串）的长度。可见，模式中相似部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。4.串的应用——KMP模式匹配算法4.串的应用——KMP模式匹配算法计算next[j]的方法：当j=1时，next[j]=0；//next[j]=0表示根本不进行字符比较当j1时，next[j]的值为：模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度加1。当无首尾相同的子串时next[j]的值为1。next[j]=1表示从模式串头部开始进行字符比较j=1时,next[j]＝0；j=2时,next[j]＝1；j=3时,t1≠t2，因此，k=1；j=4时,t1＝t3，因此，k=2；j=5时,t1＝t4，因此，k=2；以此类推。4.串的应用——KMP模式匹配算法j12345678模式串abaabcacnext[j]01122312voidGetNext(chart[]){next[1]=0;j=1;k=0;while(jt[0])if((k==0)||(t[j]==t[k])){j++;k++;next[j]=k;}elsek=next[k];}求模式串t的next函数值算法4.串的应用——KMP模式匹配算法1.在串s和串t中分别设比较的起始下标i和j；2.循环直到s中所剩字符长度小于t的长度或T中所有字符均比较完毕2.1如果s[i]=t[j]，继续比较S和T的下一个字符；否则2.2将j向右滑动到next[j]位置，即j=next[j]；2.3如果j=0，则将i和j分别加1，准备下一趟比较；3.如果t中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；4.串的应用——KMP模式匹配算法例：设主串s=abcabcabd，模式串p=abcabd