【数据结构】模式串匹配
串详解含统考真题
名词解释
主串：一段字符串。eg:S=‘moshichuanpipei’
子串：主串中连续的一部分。eg:‘moshichuan’、‘pipei’
模式串：一段字符串，实际场景中远短于主串。eg:‘shich’、‘pipep’
模式串匹配：在主串中找到与模式串相同的子串,并返回其(第一次)出现位置。
前缀：除最后一个字符外，字符串的所有头部子串
后缀：除第一个字符外，字符串的所有尾部子串
部分匹配值：最长相等的前后缀长度
朴素算法
算法思想：如果我们想要在主串S='moshichuanpipei’中找到模式串T='shich’或T=‘pipep’,那么最直接且简单的方法就，遍历S的所有长度和T相同的子串，寻找是否有相同的
算法实现：
int Index(SString S,SString T){int i=1,j=1; //i,j分别指向S和T将要比较的字符while(i<=S.length && j<=T.length){if(S.ch[i]==T.ch[j]){i++;j++; //比较后继字符}else{i=i-j+2;j=1;//指针后移开始下一轮匹配}}if(j>T.length) //匹配成功，返回第一次出现起始位置return i-T.length;else //匹配失败return 0;
}
分析复杂度：假设主串长度为15，模式串长度为5，最好情况为：第一个子串就匹配成功eg:S=‘aaaabaaaaaaaaaa’,T=‘aaaab’，最坏情况为：比较了所有长度为5的子串也没能和模式串匹配，且模式串和每个子串都比较了5个字符,eg:S=‘aaaaaaaaaaaaaaa’,T=‘aaaab’，
抽象表示主串长n，模式串长m，在匹配过程中字符比较的时间为O(1)，那么最好时间复杂度为O(m),最坏时间复杂度为O(n*m)；
在朴素算法中遇到较坏情况时S的指针i需要多次回溯，导致S与T串有很多字符多次没必要的重复比较，浪费了计算时间，所以我们需要更优的算法(KMP算法)来应对这种情况
KMP算法
算法目的：对于S=‘aaaaaaaaaaa’,T=‘aaaab’这种情况，
第一轮匹配时面对的情况是S=’???..??’,T=’???’，匹配后发现S与T前4个字符相同，在第5个字符不同，此轮匹配失败
第二轮匹配时面对的情况是S=‘aaaaa???..??’,T=‘aaaab’，此时通过观察在下一轮匹配时我们希望能将S的第六个子串与T匹配，而不是第二个。这就是KMP算法的目标。
算法思想：可以发现若要实现上述目的，匹配失败S的指针不需要回溯，而是改变T的指针使模式串向后移动,
即
第一轮结束后 第二轮开始时 i iS aaaaa???... S aaaaa???... T aaaab T aaaabj j
这样移动的原因是aaaaa长为4的后缀与aaaab长为4的前缀匹配成功。
细心话的会在这里发现两个问题：1.如何计算模式串后移几位(求next数组)；2.仍然有一次重复匹配(KMP的优化)
这一小节主要是理解KMP思想，所以先带着两个问题阅读，
枚举求next数组：
第5个字符不匹配i iS aaaaa???... S aaaaa???... T aaaab T aaaabj j 向后移动1位，使j=4
第4个字符不匹配i iS aaac????... S aaac????... T aaaa? T aaaa?j j 向后移动1位，使j=3
第3个字符不匹配i iS aac?????... S aac?????... T aaa?? T aaa??j j 向后移动1位，使j=2
第2个字符不匹配i iS ac??????... S ac??????... T aa??? T aa???j j 向后移动1位，使j=1
第1个字符不匹配i iS c???????... S ca??????... T a???? T a????j j 向后移动1位，使j=1,i++
定义next数组为：当S[i]!=T[j]使，要使j=next[j]，来实现模式串的移动
由于每个人字符串定义方式不同，所以求得的next数组也会不同，但都是为了改变j，来移动模式串到合适的位置
此时求得next数组为
| T | a | a | a | a | b |
|---|---|---|---|---|---|
| j | 1 | 2 | 3 | 4 | 5 |
| next[j] | 0 | 1 | 2 | 3 | 4 |
此处next[1]=0是为了与next[2]区分，根据枚举两者都要j=1，但前者还需要i++,为了方便代码编写使其值为0
综上所述，KMP算法的原理就是，主串不动，通过一个辅助数组next[]，来实现不同情况下模式串的移动，以减少重复匹配的次数
当前将next作为已知信息，来完成KMP算法的实现
int Index_KMP(SString S,SString T,int next[]){int i=1,j=1;while(i<=S.length && j<=T.length){if(j==0||S.ch[i]==T.ch[j]){i++;j++; //比较后继字符}elsej=next[j]; //更新指针开始下一轮匹配}if(j>T.length) //匹配成功，返回第一次出现起始位置return i-T.length;else //匹配失败return 0;
}
与朴素算法的区别只在与匹配失败后如何更新指针。
分析复杂度：主串长n，模式串长m，在匹配过程中字符比较的时间为O(1),求解next数组时间为O(m)，那么最好时间复杂度为O(m),最坏时间复杂度为O(n+m)；
理解以上过程那么就理解了KMP算法的原理，即通过改变更新指针的方法来减少重复比较次数，其核心在于求解和利用辅助数组next[]
问题①求解next[]
手算next[]
为了理解next求解过程，不妨再用几个模式串枚举得其next[]数组，来观察next数组与模式串的关系
通过枚举得到
T a a a a b
next 0 1 2 3 4
T a b c a c
next 0 1 1 1 2
T a b a a b c a b a
next 0 1 1 2 2 3 1 2 3
此时仍较难发现其中规律，但似乎与模式串的前后缀匹配有关系，可以试试再求出与前后缀匹配有关的部分匹配值，用pm表示
T a a a a b
PM 0 1 2 3 0
next 0 1 2 3 4T a b c a c
PM 0 0 0 1 0
next 0 1 1 1 2T a b a a b c a b a
PM 0 0 1 1 2 0 1 2 3
next 0 1 1 2 2 3 1 2 3
此时可以发现
next[j]=pm[j-1]
若结合之前枚举的过程来看，可以发现
移动位数=已匹配字符-对应的部分匹配值
现在我们就可以不需要通过枚举来求得模式串对应的next数组
以T='abaabcaba’举例
| T | a | b | a | a | b | c | a | b | a |
|---|---|---|---|---|---|---|---|---|---|
| pm | 0 | 0 | 1 | 1 | 2 | 0 | 1 | 2 | 3 |
为了向next靠齐，在pm前加一位-1
| T | a | b | a | a | b | c | a | b | a | |
|---|---|---|---|---|---|---|---|---|---|---|
| pm | 0 | 0 | 1 | 1 | 2 | 0 | 1 | 2 | 3 | |
| pm_next | -1 | 0 | 0 | 1 | 1 | 2 | 0 | 1 | 2 | 3 |
| next | 0 | 1 | 1 | 2 | 2 | 3 | 1 | 2 | 3 |
上表中next为我们需要的辅助数组，因为next时pm_next每一位加1得到的，更新T指针时位数也会差1，所以next用于模式串从1号位置开始存储，而pm_next则可用于模式串从0号位置开始存储的情况，主要理解其计算过程，使用时视情况选择即可
综上所述：手算next数组的方法为，①先求得模式串每一个前缀对应的部分匹配值pm，②再在pm前加一位-1得到pm_next，③最后在pm_next的每一位加1得到next数组。
代码计算next[]
算法目的：T长为m，在O(m)的时间内求得，T对应的next数组。
先尝试模拟手算，发现计算pm值时需要经常比较前后缀，最坏时间复杂度会接近O(m^2)，这种思路不可行
重新审视next数组
T a a a a b
next 0 1 2 3 4
T a b c a c
next 0 1 1 1 2
T a b a a b c a b a
next 0 1 1 2 2 3 1 2 3
发现假设S为T[1]到T[j-1]组成的串，那么next[j]=S的最长相等前后缀长度+1，其中next[1]=0;
例如
j
T a b a a b c a b a
next 0 1 1 2 2
当j=5时，next[4]='abaa'最长前后缀长度+1=2
核心
j
T a b a a b c a b a
next 0 1 1 2 2
当j=6时求解next[6],已知next[5]=2,根据next性质可以得到'abaa'最长前后缀长度为next[5]-1=1,'a'='a'
问题转换为，已知T1=T4，求'T1T2T3T4T5'最长前后缀长度
此时T5=T2,那么'T1T2T3T4T5'='T1T2T3T1T2'最长前后缀长度2，next[6]=2+1=3
得出,设k=next[j],若Tj=Tk,则next[j+1]=next[j]+1
j
T a b a a b c a b a
next 0 1 1 2 2 3
当j=7时求解next[7],已知next[6]=3,根据next性质可以得到'abaab'最长前后缀长度为next[6]-1=2,'ab'='ab'
问题转换为，已知T1T2=T4T5，求'T1T2T3T4T5T6'最长前后缀长度，
此时T6≠T3,只能得到'T1T2T3T4T5T6'='T1T2T3T1T2T6',又因为next[3]=1,且T6≠T1,算出此时最长前后缀长度0，next[7]=0+1=1
得出,设i=j,k=next[j],若Ti≠Tk,则令j=next[j],k=next[j],比较Ti与Tk直到Ti=Tk或者j=0
此时next[i+1]=next[j]+1
按上诉方法求next数组就不需要重复比较前后缀，只需要利用之前计算得到的next值
算法思想：
由上面两条结论
设k=next[j],若Tj=Tk,则next[j+1]=next[j]+1
设i=j,k=next[j],若Ti≠Tk,则令j=next[j],k=next[j],比较Ti与Tk直到Ti=Tk或者j=0，此时next[i+1]=next[j]+1
总结得
计算next[j+1]时，应该设i=j+1,k=next[j]，循环比较Ti-1与Tk，若Ti-1=Tk，退出循环；若Ti-1≠Tk,则令j=next[j],k=next[j],直到i-1=Tk或者j=0，退出循环；最后next[i]=next[j]+1;
算法实现：
求next[j+1]的实现过程中，用i记录j，用j记录next[j]，当j==0或者ch[i]==ch[j]，i++,j++,next[i]=j;就相当于next[j+1]=next[j]+1;
void get_next(int next[],SString T){int i=1,j=0;next[1]=0; //初始化while(i<T.length){if(j==0||T.ch[i]==T.ch[j]){i++,j++;next[i]=j; //若Ti=Tj,next[i]=next[j]+1}else j=next[j]; //否则令j=next[j]}
}
问题②KMP的优化
回忆朴素算法和kmp算法
int Index_KMP(SString S,SString T,int next[]){int i=1,j=1; //i,j分别指向S和T将要比较的字符while(i<=S.length && j<=T.length){if(j==0||S.ch[i]==T.ch[j]){i++;j++; //比较后继字符}else{j=next[j]; //更新指针开始下一轮匹配}}if(j>T.length) //匹配成功，返回第一次出现起始位置return i-T.length;else //匹配失败return 0;
}int Index(SString S,SString T){int i=1,j=1; //i,j分别指向S和T将要比较的字符while(i<=S.length && j<=T.length){if(S.ch[i]==T.ch[j]){i++;j++; //比较后继字符}else{i=i-j+2;j=1;//指针后移开始下一轮匹配}}if(j>T.length) //匹配成功，返回第一次出现起始位置return i-T.length;else //匹配失败return 0;
}
两者形式上很相似，唯一的区别在于匹配失败后如何更新指针，所以在一般情况下朴素算法的时间复杂度也会近似为O(n+m)。eg:S=‘fffffabcde’ T=‘abcde’，因此朴素算法至今仍被采用。
为了能进一步优化KMP，先找出它的问题
第一轮结束后 第二轮开始时 i iS aaaba???... S aaaba???... T aaaab T aaaabj j
按上诉KMP算法在第二轮开始时会比较S[4]与T[3],发现不匹配后比较S[4]与T[2],由发现不匹配后比较S[4]与T[1],之后再比较S[5]与T[1]
在我们有了next数组后知道’aa’最长相等前后缀长度为1形如’T1T1’；‘aaa’最长相等前后缀长度为2形如’T1T1T1’；‘aaaa’最长相等前后缀长度为3形如’T1T1T1T1’；所以我们希望第二轮开始时能直接比较S[5]与T[1]
那么就需要调整更新指针的方法，即优化next数组
出现上述问题原因在于，存在T[j]=T[next[j]]，消除这个问题只需要将next[j]修正为next[next[j]],直到两者不相等，令新数组为nextval
算法实现：
void get_nextval(int nextval[],SString T){int i=1,j=0;nextval[1]=0; //初始化while(i<T.length){if(j==0||T.ch[i]==T.ch[j]){i++,j++;if(T.ch[i]!=T.ch[j]) nextval[i]=j;else nextval[i]=nextval[j];}else j=nextval[j];}
}
完整测试代码
#include本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！