数据结构第4章[串].ppt

第4章 串 ;本章要点;4.1.1 串的逻辑结构;课堂练习;4.1.2 串的基本运算（1）;4.1.2 串的基本运算（2）;课堂练习：;本章要点;4.2.1 串的顺序存储及基本运算的实现;存储表示;基于串的顺序存储结构的运算实现（1）;基于串的顺序存储结构的运算实现（2）;基于串的顺序存储结构的运算实现（3）;课堂练习;算法代码;本章要点;1，什么是模式匹配？ 假设有两个字符串ob和pat，若要在ob串中查找与pat串相等的子串，则称ob为主串，pat为模式串，并称这个运算为模式匹配. 2，模式匹配函数 int find（string pat）//在串对象中，查找一个与串pat相同的子串，找到，返回其位置，否则返回－1。 int StrIndex_BF　(int k, String p); //简单模式匹配 int StrIndex_KMP(int k, String p) ; //KMP算法; 算法思想： 设主串s=“ababcabcacbab”，模式t=“abcac”，匹配过程如下???所示：;设主串s=“ababcabcacbab”，模式t=“abcac”;Brute－Force算法思想：;find( String obj,string pat) //从主串的第0个位置的字符开始比较 { int i=0,j=0; if(obj.curlen ==0 || pat.curlen == 0) //主串或pat为空 return -1; while(i = obj.curlen j = pat.curlen) //逐趟比较 { if (obj.str[i] == pat.str[j]) { i++; j++; } else { i=i-j+1; j=0; } } if(j == pat.cursize) return i-pat.cursize; return -1; };模式匹配算法要点：;;模式匹配算法要点：;1，KMP算法的由来 由D.E.Knuth，J.H.morris，V.R.pratt三个共同设计，是对Brute－Force算法的改进。 2， KMP算法 设主串s=“aabcbabcaabcaababc”，子串t=“abcaababc”，下图是一个利用next函数进行匹配的过程示意图。 ;;在假设已有next函数情况下，KMP算法如下： int findKMP(int k, String p,int f[])　 { int i=0,j=0,pos; while(iob.size-1 jpat.size-1) { if (j== -1 ‖ob.str[i] == pat.str[j]) { i++; j++; } else j=f[j]; } return( j= pat.size-1 ? i-j+1 : -1) }