编辑代码

-- 获取字符串的长度（任何单个字符长度都为1）
function getStringLength(inputstr)
    if not inputstr or type(inputstr) ~= "string" or #inputstr <= 0 then
        return nil
    end
    local length = 0  -- 字符的个数
    local i = 1
    while true do
        local curByte = string.byte(inputstr, i)
        local byteCount = 1
        if curByte > 239 then
            byteCount = 4  -- 4字节字符
        elseif curByte > 223 then
            byteCount = 3  -- 汉字
        elseif curByte > 128 then
            byteCount = 2  -- 双字节字符
        else
            byteCount = 1  -- 单字节字符
        end
        -- local char = string.sub(inputstr, i, i + byteCount - 1)
        -- print(char)  -- 打印单个字符
        i = i + byteCount
        length = length + 1
        if i > #inputstr then
            break
        end
    end
    return length
end
--字符串转换为字符数组
--注入string table里面
function toCharArray(str)
    str = str or ""
    local array = {}
    local len = string.len(str)
    local index = 0
    while str do
        local fontUTF = string.byte(str,1)

        if fontUTF == nil then
            break
        end

        local byteCount = 0
        if fontUTF > 0 and fontUTF <= 127 then
            byteCount = 1
           elseif fontUTF >= 192 and fontUTF < 223 then
            byteCount = 2
           elseif fontUTF >= 224 and fontUTF < 239 then
            byteCount = 3
           elseif fontUTF >= 240 and fontUTF <= 247 then
            byteCount = 4
        end
        local tmp = string.sub(str,1,byteCount)
        -- 这里为了方便下面的算法,数组下标统一从0开始计算
        array[index] = tmp
        index = index + 1
        str = string.sub(str,byteCount + 1,len)
    end
    return array
end

local function RK(mainStr,patternStr)
	local m = getStringLength(mainStr)
	local n = getStringLength(patternStr)
	local hash = {}
	local mTable = {}
	local a1 = toCharArray(mainStr)
	local b1 = toCharArray(patternStr)
	local s = 1;
	for i=0,n do -- 将字符串转换成n进制的数字进行存储，方便后面直接取出
		mTable[i] = s
		s = s*n
	end
	for i=0,m-n do
		s = 0
		for j=0,n-1 do
            --  - string.byte("a") 这个好像是多余的
            -- local byte = string.byte(a1[i+j]) - string.byte("a")
            local byte = string.byte(a1[i+j])
			s = s + byte*mTable[n-j]
		end
		hash[i]=s
	end

	s=0
	for j=0,n-1 do
        -- local byte = string.byte(b1[j]) - string.byte("a")
        local byte = string.byte(b1[j])
		s= s + byte*mTable[n-j];
	end
	for j=0,m-n do
		if hash[j]==s then
			return j+1
		end
	end
	return -1
end

local mainStr = "在我这里面查找需要查找的串"
local patternStr = "需要查找的串"
print("查找到的位置在第 "..RK(mainStr,patternStr).." 个(下标从1开始计算)");