|
子串定位运算 串是特殊的线性表故顺序串和链串上实现的运算分别与顺序表和单链表上进行的操作类似 C语言的串库<stringh>里提供了丰富的串函数来实现各种基本运算因此我们对各种串运算的实现不作讨论利用串函数实现串的基本运算部分内容【参见练习】 下面讨论在顺序串和链串上实现的子串定位运算 子串定位运算 子串定位运算类似于串的基本运算中的字符定位运算只不过是找子串而不是找字符在主串中首次出现的位置此运算的应用非常广泛 【例】在文本编辑中我们经常要查找某一特定单词在文本中出现的位置解此问题的有效算法能极大地提高文本编辑程序的响应性能 子串定位运算又称串的模式匹配或串匹配 目标（串）和模式（串）在串匹配中一般将主串称为目标（串）子串称为模式（串） 假设T 为目标串P为模式串且不妨设 T=ttt…tn P=ppp…pm(＜m≤n) 串匹配串匹配就是对于合法的位置（又称合法的位移）≤i≤nm依次将目标串中的子串titi+…ti+m和模式串ppp…pm进行比较 ①若titi+…ti+m＝ppp…pm则称从位置i开始的匹配成功或称i为有效位移 ②若titi+…ti+m≠ppp…pm则称从位置i开始的匹配失败或称i为无效位移 因此串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移 注意 有些应用中要求求出P在T中所有出现的有效位移 顺序串上的子串定位运算（）朴素的串匹配算法的基本思想 即用一个循环来依次检查nm+个合法的位移i（≤i≤nm）是否为有效位移 具体过程【参见动画演示】 （）顺序串上的串匹配算法 以下以第二种定长的顺序串类型作为存储结构给出串匹配的算法 #define MaxStrSize //该值依赖于应用由用户定义 typedef struct{ char ch[MaxStrSize]; //可容纳个字符并依次存储在ch[n]中 int length; }SeqString; int Naive StrMatch(SeqString TSeqString P) {//找模式P在目标T中首次出现的位置成功返回第个有效位移否则返回 int ijk; int m=Plength; //模式串长度 int n=Tlength; //目标串长度 for(i=;i<=nm;i++){ //<=i<=nm是合法的位移 j=;k=i; //下面用while循环判定i是否为有效位移 while(j<m&&Tch[k]==Pch[j]{ k++;j++; } if(j==m) //既T[ii+m]=P[m] return i; //i为有效位移否则查找下一个位移 }//endfor return ; //找不到有效位移匹配失败 }//NaiveStrMatch （）算法分析 ①最坏时间复杂度 该算法最坏情况下的时间复杂度为O((nm+)m) 分析当目标串和模式串分别是anb和amb时对所有nm+个合法的位移均要比较m个字符才能确定该位移是否为有效位移因此所需比较字符的总次数为（nm+）m ②模式匹配算法的改进 朴素的串匹配算法虽然简单但效率低其原因是在检查位移i是否为有效位移时没有利用检查位移ii…时的部分匹配结果 若利用部分匹配结果模式串右滑动的距离就不会是每次一位而是每次使其向右滑动得尽可能远这样可使串匹配算法的最坏时间控制在O（m+n）数量级上具体可【参阅有关文献】 链串上的子串定位运算用结点大小为的单链表做串的存储结构时实现朴素的串匹配算法很简单只是现在的位移shift是结点地址而非整数且单链表中没有存储长度信息若匹配成功则返回有效位移所指的结点地址否则返回指针具体算法如下 LinkStrNode *LinkStrMatch(LinkString TLinkString P) {//在链串上求模式P在目标T首次出现的位置 LinkStrNode * shift*t*p; shift=T; //shift表示位移 t=shift;p=P; while(t&&p) { if(t>data==p>data){ //继续比较后续结点中字符 t=t>next; p=p>next; } else{ //已确定shift为无效位移 shift=shift>next; //模式右移继续判定shift是否为有效位移 t=shift; p=P; } }//endwhile if(p==NULL) return shift; //匹配成功 else return NULL; //匹配失败 } 该算法的时间复杂度与顺序表上朴素的串匹配算法相同 |
