字符串模式匹配算法（数据结构）

主串被搜索的字符串模式串搜索目标的字符串字符串的模式匹配在主串中找到与模式串相同的子串朴素模式匹配算法将主串中长度与模式串相同的子串与模式串一一对比在长度为n的主串中长度为m的子串有n-m1个#index基本操作中的方法intIndex(SString S,SString T){inti1,nstrLength(S),mStrLength(T);SString sub;while(in-m1){SubString(sub,S,i,m);if(StrCompare(sub,T)!0)i;elsereturni;//返回匹配成功子串的起始位置}return0;}#双指针算法实现intIndex(SString S,SSttring T){inti1,j1;while(iS.lengthjT.length){ifS.ch[i]T.ch[j]){i;j;//相同继续比较后续字符}else{ii-j2;//主串指针初始1j1;//模式串指针归位}}if(jT.length)returni-T.length;elsereturn0;}最坏的情况每个子串都要对比m个字符共n-m1个子串复杂度 O ((n−m1) m) O(nm)KMP算法intIndex_KMP(SString S,SString T,intnext[]){inti1,j1;while(iS.lengthjT.length){if(j0||S.ch[i]T.ch[j]){i;j;//继续比较后继字符}else{jnext[j];if(j0){i;j;}}//模式串向右移动}if(jT.length)returni-T.length;//匹配成功返回主串起始下标elsereturn0;}最坏时间复杂度O(mn)#求next数组next[1]无脑写0next[2]无脑写1在不匹配的位置前边划一根美丽的分界线。模式串一步一步往后退直到分界线之前“能对上”或模式串完全跨过分界线为止。此时 j 指向哪儿next数组值就是多少#求nextval数组nextval[1]0;for(intj2;jT.length;j){if(T.ch[next[j]]T.ch[j])nextval[j]nextval[next[j]];elsenextval[j]next[j];}