数据结构4串4-(精选·公开·课件).ppt

串是由零个或多个字符组成的有限序列。 一般记为：s = “ a1a2…an” 串名 串值 串的长度：串中字符的数目。 空串：长度为零的串。用“?”来表示空串。 4.7 4.8 4.16 改进算法(KMP算法)： int index_kmp(SSring S，SString T ) //利用模式串t的next函数值求T在主串S中首次出的位置 { i = 1； j=1； while (i≤S[0] j≤T[0]) if (j= =0 || S[i] = = T[j]) { i ++； j++ }; else j =next[j]； if (jT[0]) return(i - T[0])； else return(0) } // index_kmp (1) 由定义得知 next[1] = 0 (2) 已知 next[j] = k， 如何求next[j+1]? 由于next[j] = k，则有下面的等式成立： “p1 … pk-1” = “pj-k+1 … pj-1” ①若 pk=pj 则有 ：“p1 … pk” = “pj-k+1 … pj” next[j+1] = next[j] + 1 = k + 1 p1 p2……pk-1 …… pj-k+1 …… pj-1 pj pj+1 ……pn [问题2] 如何求next[j]函数： (b) 若 pk≠pj ， 则将求函数next的问题看成是一个模式匹配的过程。 由于已有 “p1 … pk-1” = “pj-k+1 … pj-1” 则当pj ≠pk时，将模式串向右滑动，使第next[k]个字符和主串中的第j个字符相比较。 若next[k]=k′， 且pj = pk′ 则： next[j+1] = k′+ 1 = next[k]+1 若pj ≠ pk′， 则使第next[k′]个字符和pj对齐，… 依此类推。 S1 S2 …… Si-j+1 …… Si-j+k-1 …… Si-k+1 …… Si-1 Si … ≠ P1 P2……Pk-1 …… Pj-k+1 …… Pj-1 Pj ≠ k=next[j] P1 …… Pk-1 Pk 当Pj≠Pk时 ，Pj应与那一个P 比较？设与P k’比较：则 P1 P2……Pk-1 …… P j-kj+1 …… Pj-1 Pj P1 ……… Pk’-1 Pk’ 即： k’=next[k] void get_next(Sstring T，int next[]) // 求模式串T的next值并存入数组next[1..T[0]]中 { j =1； k = 0；next[j] = k；//初始化 while (j T[0]) if (T[j] = =T[k] || k==0) { k++； j++ ； next[j] = k； // next[j+1] = k+1 } else k = next[k]; } // get_next * * * * 一. 串的抽象数据类型的定义 二. 串的表示和实现 三. 串的模式匹配算法 串是字符串的简称。它是一种特殊的线性表，线性表的每个元素仅由一个字符组成。 子串：串中任意个连续的字符组成的子序列称为该串的子串。 主串：包含子串的串相应地称为主串。 例：s1 = “12ab3AB45ABC” ------- 主串 s2 = “AB” ------- 子串 字符在串中的位置：字符在字符串序列中的序号 子串在主串中的位置：子串在主串中的第一次出现时，子串中的第一个字符在主串中的位置。 串相等：两个串的长度相等，并且各个对应位置的字符都相等。 (1)判等函数：EQUAL(s，t) (2)求长函数：LENGTH(s) (3)连接函数：CONCAT(s，t) (4)求子串函数：SUBSTR(s，start，len) 若 1≤star