《数据结构》-串

第四章 串,第四章 串,4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法,定义： 或称为字符串，是由零个或多个字符组成的有限序列，一般记为s= a1a2an (n=0)其中s是串的名，用双引号括起来的字符序列是串的值；ai(1=i 0) / if return 0; / S中不存在与T相等的子串 / Index,n = StrLength(S); m = StrLength(T); i = pos;,while ( i 0) printf(st1st2n); if(k0) printf(st1 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i m,T 串,一、简单算法,先比较模式串的第一个字符， 再比较模式串的最后一个字符， 最后比较模式串中从第二个 到第 n-1 个字符。,二、首尾匹配算法,int Index_FL(SString S, SString T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始点 else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else return 0; ,检查中间字符的匹配情况,k = 1; j = 2; while ( j tLength / 重新开始下一次的匹配检测,KMP算法的时间复杂度可以达到O(m+n),三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法,KMP算法：每一趟匹配过程中出现不等时，不需回溯指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的距离后，继续比较.,KMP算法示意图,主串 a b a b c a b c a c b a b模式串 a b c a c,第一趟匹配 a b a b c a b c a c b a b,a b c,i=3,j=3,第二趟匹配 a b a b c a b c a c b a b,a b c a c,i=7,j=5,第三趟匹配 a b a b c a b c a c b a b,a b c a c,i=10,j=5,S s1 s2 si-j+1 si-j+2 .si-k+1 si-k+2 si-1 si sn P p1 p2 p3 pj-k+1 pj-k+2 pj-1 pj, P向右滑动 p1 p2 pk-1pk,由p1 p2 .pk-1= Si-k+1 Si-k+2 .Si-1pj-k+1 pj-k+2 .pj-1= Si-k+1 Si-k+2 .Si-1推得 p1 p2 .pk-1 = pj-k+1 pj-k+2 .pj-1,nextj仅与模式串相关,表明当模式串中第j个字符与主串中相应字符匹配“失效”时,在模式中需重新和主串中该字符进行比较的字符的位置,nextj= 模式串前段p1 pj-1中头尾相同 的最长头串或尾串的长+1,0 j =1nextj= maxk|0kj , p1 pk-1 =pj-k+1pj-1 1 其他情况,next0=0; next1=1; next2=1;next3=2; next4=2; next5=3next6=1; next7=2;,int Index_KMP(SString S, SString P, int pos) / 1posStrLength(S) i = pos; j = 1; while (i P0) return i-P0; / 匹配成功 else return 0; / Index_KMP,穷举的模式匹配算法时间代价： 最坏情况比较n-m+1趟，每趟比较m次，总比较次数达(n-m+1)*m 原因在于每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。 改进的模式匹配(KMP)算法的时间代价： 若每趟第一个不匹配，比较n-m+1趟，总比较次数最坏达(n-m)+m = n 若每趟第m个不匹配，总比较次数最坏亦达到 n,如何求nextj值:j=1, nextj=0设nextj=k, 存在关系 (k nextj+1=nextj+1 (2)若 pkpj, 则 p1 p2 .pk pj-k+1 pj-k+2 .pj需往前回朔，这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串,void get_next(SString / get_next,还有一种特殊情况需要考虑：例如： S = aaabaaabaaabaaabaaab T = aaaabnextj= 01234,nextvalj=00004,void get_nextval(SString / get_nextval,4.4 串应用,文本编辑建立词索引表,小