KMP算法优化

KMP算法是根据三个发现者名字首字母缩写命名的。

图1

是一种启发式的跳过搜索算法。在搜索过程中如果搜索串有个字母与目标串不匹配，移动搜索串开头到匹配位置（特例：如果是第一个字母就不匹配，搜索串也要移动一位）。要处理就是如下这种特例。如果搜索串不匹配字符前面字符串有如下匹配模式。

图2:在不包括字母C的字符串中找出尽量长的两个子串，子串分别连接开头和结尾

就如图1最后那行所标示的：内部有2个子串“ab”相等。所以搜索串又要回退两个位置（ab的长度）如图1第4行。

如下是我对这算法的一点优化尝试，使用Lua实现：

local pattern = 'abaabcac'

local jump = {}

function CalcJump()

local i = 1

    while (i <= #pattern) do

if i == 1 then

table.insert(jump, 1)

else

local half_count = math.floor(i/2)

if string.sub(pattern, 1, half_count) == string.sub(pattern, i-half_count+1, i) then

table.insert(jump, i+1-half_count)

else

if i == 2 then

table.insert(jump, 1)

else

local half_count = math.floor((i-1)/2)

local inserted = false

for _i = half_count, 1, -1 do

if string.sub(pattern, 1, _i) == string.sub(pattern, i-_i, i-1) then

table.insert(jump, i-1-_i)

inserted = true

end

end

if not inserted then

table.insert(jump, i)

end

end

end

end

i = i + 1

    end

end

CalcJump()

function Matchs(str)

local offset = 0

while offset <= #str - #pattern do

for j = 1, #pattern do

if string.byte(pattern, j) ~= string.byte(str, offset + j) then

offset = offset + jump[j]

break

end

if j == #pattern then  --退出

print(string.sub(str, offset+1), offset)

offset = offset + 1

end

end

end

end

Matchs('abcabaaaabaabcac')

实现原理就是更细致的分析搜索串的内部匹配。使得搜索算法能以更长的步长跳跃。