文档介绍：串匹配算法
串匹配简单算法
算法1的基本思想:
匹配的定义:给出两个文字串,一个长度为n,称为正文,记为T。另一个长度为m,称为模式,记为P。在T中找出P的出现,找到一次称为发生一次匹配,P和T可能发生一次匹配、多次匹配或不匹配。
子段的划分:在长度m的模式前提下,长度为n的正文可以分为n-m+1个子段。
问题的输入:正文T和模式P,两者皆非空。
问题要求的输出结果:成功或失败的标志。成功是相对于每个独立子段的,一次匹配为一次成功,多次匹配输出多次成功的标志;而失败是相对与所有子段的,一次子段的不匹配不会输出失败的标志,只有当所有子段都不匹配时才输出失败的标志,程序算法中应该输出一次或多次成功标志再加上一个所有子段都匹配完的失败标志,或都不匹配时只输出一个失败标志。
逻辑判断中的移位问题(移位类型和移位条件):正文中存在子段内移位和子段间移位两种情况,模式中只有内部移位,可以用下标i,j,k来分别指定子段、段内字母、模式内字母,用 i++,j++,k++ 分别进行移位。段内字母和模式内字母移位同时进行,移位的条件是对应字母相等和k!=m,k=m则不再移位而输出成功标志,段间移位的条件是I<=n-m+1且正文子段与模式的对应首字母相等。
算法在最坏情况下需要比较的次数为:m(n-m+1)=O(mn)。
算法程序如下:
Begin
I ← 0
While I<=n-m+1 do
Begin
I ← I+1;j ← I;k ←1
While Tj=PK do
Begin
If k=m then return’ESS’
Else do
Begin
J ← j+1
K← k+1
End
End
End
Return ‘FAILURE’
end
算法1的举例和分析:
给定模式P: ABABC,正文T: A 。在 T中寻找于P匹配的子段。
可以看出此例中正文的子段数为5,只有在第三个子段才匹配成功。
算法2的基本思想:
算法2和算法1的思想基本相同,只是作了一点改进,它把模式P接在正文T的后面,成为TP,TP存放在数组a:array[1…(n+m)] of char,这时,P不必移动,可以减少一个指针。此时k用n+j代替,Pk用 a[n+j]代替。算法程序如下:
begin
I ← 0
Repeat
i ← i+1
j ← 1
while(j<=m)and (a[I+j-1]=a[n+j]) do
j ← j+1
until j>m
search ← I
end
在上述程序中,T存放在a:[1…n]中,P存放在a:[n+1…n+m]中,P与T不匹配时,返回值为n+1。算法2在最坏情况下的复杂性与算法1相同,在文字编辑中,算法2的内循环执行次数很少,故所需时间接近于n。
算法2的举例和分析:P: relative T: a string searching example involving relative simple text 执行算法2时,在出现匹配之前,内循环语句j ←j+1只执行两次。
P: aaaab T:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab 执行算法2时,在出现匹配之前,内循环语句j ← j+