数据结构第09讲_串的模式匹配及串的应用_C.ppt

例：求下列模式串的next[j]函数 模 式 串 T： a b a a b c a c 可能失配位 j ： 1 2 3 4 5 6 7 8 新匹配位 next[j] : 4.4.1 文本编辑 文本编辑程序用于源程序的输入和修改，公文书信、报刊和书籍的编辑排版等。常用的文本编辑程序有Word,Notepad,WPS,TC等，文本编辑的实质是修改字符数据的形式和格式，虽然各个文本编辑程序的功能不同，但基本操作是一样的，都包括串的查找、插入和删除等。 为了编辑方便，可以用分页符和换行符将文本分为若干页，每页有若干行。我们把文本当作一个字符串，称为文本串，页是文本串的子串，行是页的子串。 我们采用堆存储结构来存储文本，同时设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符，同时建立页表和行表存储每一页、每一行的起始位置和长度。 假设有如下源程序： FUNC max(x，y：integer)：integer; VAR z：integer; BEGIN ?? IF xy THEN z:=x; ?? ELSE z:=y; ?? RETURN(z); END; 该程序输入内存后放到一个堆中，如下图所示。其中↙为换行符。 练1：串是由 字符组成的序列，一般记为 。 练4：令模式串 s=‘a a a b’ t=‘a b c a b a a’ u=‘a b c a a b b a b c a b a a c b a c b a’ 分别求出他们的next函数值。 练5：从串S中删除所有和串T相同的子串。 此题的操作等同于“以空串置换串S中所有和串T相同的子串。” 练6：顺序串上的插入insert(S,i,T) 要将T插入到S中第i个位置，则S串中第i个位置开始，一直到最后的字符，每个都要向后移动若干位，移动的位数为T串长度。具体实现如图。 练7：链串上的插入insert(S,i,T) 仅考虑结点大小为1的链串，要在第i个位置插入，先用一个指针指向S串的第i-1个位置，然后在T串中用另一个指针指向表尾，具体实现如图： 第4章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.3.1 求子串位置的定位函数 4.3.2 模式匹配的一种改进算法 4.4 串操作应用举例 4.3 串的模式匹配算法 4.3.1 求子串位置的定位函数 又称模式匹配或串匹配，应用非常广泛。 在串匹配中，假设S为目标串，P为模式串： S=‘s1s2...sn’ P=‘p1p2…pm’ 串的匹配实际上是根据 1≤i≤n-m+1 依次将 S 的子串 S’[i..i+m-1] 和 P[1..m] 进行比较，若 S’[i..i+m-1] = P[1..m]，则称从位置i开始的匹配成功；反之，匹配失败。 上述的位置i又称为位移， 当S’[i..i+m-1] = P[1..m]时，i称有效位移； 当S’[i..i+m-1]≠ P[1..m]时，i称无效位移。 这样，串匹配问题可简化为是找出某给定模式串 P 在给定目标串 S 中首次出现的有效位移。 串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。 基本思想：用一个循环来依次检查 n-m+1个合法的位移i(1≤i≤n-m+1)是否为有效位移。 算法段： for(i=1;i=n-m+1;i++) if(S[i..i+m-1]=P[1..m]) return i; 例： 设pos=1； 模式串T=‘abcac’ 例：模式匹配的算法 int Index(SString s,SString p,int pos){ j=1; i=pos; while (i= s[0] j= p[0] ) { if(s[i]= =p[j]){ i++; j++;} //继续比较后续字符 else { i=i-j+2; j=1; } //指针回溯到下一首位，重新开始匹配 } if(j p[0]) return i-p[0]; //匹配成功 else return 0; } // Index 相当于子串向右滑动一个字符位置 匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。 算法简单并易于实现，但在某些情况下时间效率不高，主要的原因是主串下标i在若干个字符序列比较相等后只要有一个字符比较不相等时便需要把下标i的值回退。 算法的最坏