首页 > 代码库 > [考研系列之数据结构]线性表之字符串
[考研系列之数据结构]线性表之字符串
基本概念
串(字符串) | 由0个或多个字符组成的有限序列,例如s="hello world" |
串名 | 上例中的s |
子串 | 某串任意连续字符组成的子序列,称为此字符串的子串 |
空串 | 0个字符的串,s="" |
空格串 | 由一个或多个字符组成的串 |
模式匹配算法
作用 | 定位某子串T在字符串S中的位置 |
主串 | S |
模式串 | T |
针对模式匹配算法从简到难我们需要了解两种算法:
[1] 朴素的模式匹配算法
[2] KMP匹配算法
[2] KMP匹配算法
朴素的模式匹配算法:
所谓朴素就是简单,这是一种简单的模式匹配。让我们从一个栗子来看朴素的模式匹配算法是如何进行的。
主串S="ababcabcacbab"
模式串T="abcac"
模式串T="abcac"
直接截图严书了。
对于朴素的模式匹配算法,我们依次将T的第j个字符和S的第i个字符比较,如果
T[i]==S[j] | 匹配成功 | ++i;++j;进行下一个字符的匹配 |
T[i]!=S[j] | 匹配失败 | T需要重新从第0个字符开始匹配 |
S的j也需要回溯到某个位置 |
这里关键是j应该回退到那个位置。
上面的草图画出了S和T在某个位置匹配失败了,那么i需要退回到0而j应该退回到x+1;通过很简单的计算
j-x=i
x+1=j-i+1
x+1=j-i+1
下面,什么时候算法结束?
当T或者S已经匹配了最后一个字符的时候,程序结束。当T匹配到最后一个字符且仍然匹配成功那么整个匹配就是成功的,反之失败。
下面给出C++风格的代码:
int index(String S,String T)
{
int i=0;
int j=0;
while(i<T.length&&j<S.length)
{
if(T[i]==S[j]) //本次字符匹配成功
{
++i;++j;
}
else //本次字符匹配失败
{
j=j-i+1;i=0;
}
}
if(i==T.length) //成功匹配
return j-i;
return 0;
}
{
int i=0;
int j=0;
while(i<T.length&&j<S.length)
{
if(T[i]==S[j]) //本次字符匹配成功
{
++i;++j;
}
else //本次字符匹配失败
{
j=j-i+1;i=0;
}
}
if(i==T.length) //成功匹配
return j-i;
return 0;
}
KMP匹配算法
对于朴素的匹配算法,在最差的情况下,它只能取得O(S.length*T.length)的算法复杂度,而基于朴素模式匹配算法的KMP能在O(T.length+S.length)内完成。
让我们先想想,朴素的匹配算法最耗时的操作是什么?
是j的回溯,j需要回溯到j-i+1的位置进行下一轮匹配。那么如何能减少j的回溯长度呢?依然以朴素匹配算法中的实例为栗子。
我们看到T匹配到"abca"时,匹配失败,如果按照朴素匹配算法,下面S会跳到"bcbb..."的第二个位置进行匹配,但是很明显,第一次就会匹配失败,第三次"cbb..."依然会在第一次匹配的时候失败,那么这两轮匹配其实是没有意义的,因为从模式串T看来,由于是在第四个位置匹配失败的,但是它前面的三个位置是匹配成功的,它知道下一轮匹配的S的首字符是T[1]="b",再下次是T[2]="C"。那么,我们通过研究T的规律是可以减少回溯减少不必要的匹配轮数的。
下面正式进入KMP算法。首先来一段理论的说明:
KMP匹配算法主要步骤有两步
[1] 求next数组
[2] 利用next数组进行匹配
[2] 利用next数组进行匹配
下面首先让我们看看next数组
含义:next[j]表示当T[j]和S[i]失配的时候,在T中需要和S[i]重新比较的字符的位置,也就是会比较T[next[j]]和S[i]的关系
定义:
[待续]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。