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

• 主串：被搜索的字符串
• 模式串：搜索目标的字符串
• 字符串的模式匹配：在主串中找到与模式串相同的子串

朴素模式匹配算法

• 将主串中长度与模式串相同的子串与模式串一一对比
• 在长度为n的主串中，长度为m的子串有n-m+1个

#index基本操作中的方法

intIndex(SString S,SString T){inti=1,n=strLength(S),m=StrLength(T);SString sub;while(i<=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)++i;elsereturni;//返回匹配成功子串的起始位置}return0;}

#双指针算法实现

intIndex(SString S,SSttring T){inti=1,j=1;while(i<=S.length&&j<=T.length){if（S.ch[i]==T.ch[j]){i++;j++;//相同，继续比较后续字符}else{i=i-j+2;//主串指针初始+1j=1;//模式串指针归位}}if(j>T.length)returni-T.length;elsereturn0;}

• 最坏的情况，每个子串都要对比m个字符，共n-m+1个子串，复杂度 = O ((n−m+1) m) = O(nm)

KMP算法

intIndex_KMP(SString S,SString T,intnext[]){inti=1,j=1;while(i<=S.length&&j<=T.length){if(j==0||S.ch[i]==T.ch[j]){++i;++j;//继续比较后继字符}else{j=next[j];if(j==0){i++;j++;}}//模式串向右移动}if(j>T.length)returni-T.length;//匹配成功，返回主串起始下标elsereturn0;}

• 最坏时间复杂度：O(m+n)

#求next数组

• next[1]无脑写0
• next[2]无脑写1
• 在不匹配的位置前边，划一根美丽的分界线。模式串一步一步往后退，直到分界线之前“能对上”，或模式串完全跨过分界线为止。此时 j 指向哪儿，next数组值就是多少

#求nextval数组

nextval[1]=0;for(intj=2;j<=T.length;j++){if(T.ch[next[j]]==T.ch[j])nextval[j]=nextval[next[j]];elsenextval[j]=next[j];}