字符串匹配的KMP算法

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

Option Explicit

Dim I As Long, J As Long

'字符串匹配的KMP算法

Private Sub Command1_Click()

'* 需匹配的字节数组

Dim P() As Byte

'* 源文件字节数组

Dim S() As Byte

Dim txt As String

Dim Fnum As Long

txt = App.Path & "\Sample"

Fnum = FreeFile

Open txt For Binary As #Fnum

ReDim S(1 To FileLen(txt))

Get #Fnum, , S

Close #Fnum

ReDim P(1 To Len(Text1.Text) / 2)

For I = 1 To Len(Text1.Text) / 2

P(I) = CInt("&H" & Mid(Text1.Text, I * 2 - 1, 2))

Next

Print InByteArray(CInt(Text2.Text), P(), S())

End Sub

'*************************************************************************

'**函 数 名:InStrByteArray

'**输 入:P()(Byte) - 需匹配的字节数组

'** :S()(Byte) - 源文件字节数组

'**输 出:(Long) - 在源文件中匹配的位置

'**功能描述:字符串匹配的KMP算法,本函数用在字节数组中

'**全局变量:

'**调用模块:

'**作 者:不详

'**日 期:2004年07月17日

'**修 改 人:

'**日 期:

'**版 本:V1.0

'*************************************************************************

Function InByteArray(Start As Long, P() As Byte, S() As Byte) As Long

'*失败联接数组

Dim FLink() As Long

Dim pLen As Long

Dim sLen As Long

Dim flag As Boolean

pLen = UBound(P)

sLen = UBound(S)

ReDim FLink(1 To pLen)

'*KMP算法实现

'*先求得失败联接数组.设FLink(i-1)=j 则有:

'______________________________________

'* P1 P2 P3 ... Pj-1 || Pj

'* Pi-j Pi-j+1 Pi-j+2 ... Pi-2 || Pi-1

'如果Pj=Pi-1则有FLink(i)=FLink(i-1)+1

'如果Pj<>Pi-1则,找寻P的初始子串,使它与Pi-1结束的子串相匹配

'-----------------------------------------

FLink(1) = 0

For I = 2 To pLen

J = FLink(I - 1)

If J <> 0 Then

Do While P(J) <> P(I - 1)

J = FLink(J)

If J = 0 Then Exit Do

Loop

End If

FLink(I) = J + 1

Next

'-----------------------------------------

I = 1: J = 1: flag = False

For I = Start To sLen

If P(J) <> S(I) Then J = FLink(J)

If J = pLen Then

flag = True

Exit For

Else

J = J + 1

End If

Next

If flag = True Then

I = I - pLen + 1

Else

I = 0

End If

InByteArray = I

End Function

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航