如下如有误,请指出,谢谢,解释均在注释中

    参考:http://blog.csdn.net/yutianzuijin/article/details/11954939/

    1. --求前缀字符
    2. function getNext(str)
    3.     local next = {[0] = 0,[1] = 0}
    4.     local k = 0     --初始化最大前后缀长度为0
    5.     for i = 2,#str do  --从第二个字符开始，依次计算每一个字符对应的next值
    6.         --相等的话最大前后缀长度+1,否则赋值为0
    7.         if str[i] == str[k+1] then
    8.             --保存此次最大前后缀长度,保存在数组中和保存在k中给下个字符使用
    9.             k = k + 1
    10.             next[i] = k
    11.         else
    12.             k = 0
    13.             next[i] = k
    14.         end 
    15.     end
    16.     return next
    17. end
    19. function Str2CharTable(str)
    20.     local t = {}
    21.     for  chr in  string.gmatch(str, ".") do
    22.         t[#t+1] = chr
    23.     end
    24.     return t
    25. end 
    27. function KmpFind(srcStr,findStr)
    28.     local Next
    29.     Next  =  getNext(findStr)
    30.     print(table.concat(Next,","))
    31.     local indexSrcStr, indexFindStr = 1,1
    32.     while ( indexSrcStr <= #srcStr  and  indexFindStr <= #findStr ) do
    33.         if srcStr[indexSrcStr] == findStr[indexFindStr] then
    34.             indexSrcStr = indexSrcStr + 1
    35.             indexFindStr = indexFindStr + 1
    36.         else
    37.             --移动位数 = 已匹配的字符数 - 对应的部分匹配值
    38.             indexSrcStr = indexSrcStr + ( indexFindStr - Next[indexFindStr])
    39.         end 
    40.     end 
    41.     if indexFindStr > #findStr  then
    42.         return indexSrcStr - indexFindStr + 1,indexSrcStr - 1
    43.     else
    44.         return -1, -1
    45.     end
    46. end 
    49. local srcStr,findStr
    50. srcStr,findStr = Str2CharTable("BBCABCDABABCDABCDABDE"),Str2CharTable("ABCDABD")
    51. local startPos,endPos = KmpFind(srcStr,findStr)
    52. print(startPos,endPos)