基于KMP匹配算法的字符串快速匹配方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN110909214A(43)申请公布日2020.03.24(21)申请号201911120073.3(22)申请日2019.11.15(71)申请人国网安徽省电力有限公司安庆供电公司地址246000安徽省安庆市人民路170号(72)发明人冯驰蔡翔陈清萍毛峰吴丽莎陈山李超夏雨潇(74)专利代理机构上海精晟知识产权代理有限公司31253代理人孙永智(51)Int.Cl.G06F16/903(2019.01)权利要求书1页说明书5页附图1页(54)发明名称基于KMP匹配算法的字符串快速匹配方法(57)摘要本发明公开了基于KMP匹配算法的字符串快速匹配方法，涉及数据处理技术领域。本发明包括将模式串最后一个字符x与文本串进行匹配；若字符x匹配失败；采用坏字符规则移动；若字符x匹配时；采用模式串前缀与文本串比较，若模式串前缀与文本串同配，则字符串找到；若失配，则根据KMP算法得到模式串右移的距离使模式串在新位置进行一下轮的匹配。本发明通过将模式串最后一个字符x与文本串进行匹配；若字符x匹配失败；采用坏字符规则移动；若字符x匹配时；采用模式串前缀与文本串比较；降低字符匹配时间复杂度，提高匹配效率。CN110909214ACN110909214A权利要求书1/1页1.基于KMP匹配算法的字符串快速匹配方法，其特征在于，包括如下步骤：将模式串最后一个字符x与文本串进行匹配；若字符x匹配失败；采用坏字符规则移动；若字符x匹配时；采用模式串前缀与文本串比较，若模式串前缀与文本串同配，则字符串找到；若失配，则根据KMP算法得到模式串右移的距离使模式串在新位置进行一下轮的匹配；当字符x在模式串前缀中出现，而模式串在这个新位置并未使主串的字符x与模式串前缀中出现的字符x对齐，则向右增大模式串的移动距离，使主串中的字符x与模式串前缀中出现的字符x对齐，然后再进行比较；若字符x并未在模式串前缀中出现，采用好字符规则直接跳过该区域获得最大的右移距离。2.根据权利要求1所述的基于KMP匹配算法的字符串快速匹配方法，其特征在于，所述好字符规则还需增加一个好字符数组GC以记录模式串最末字符在字符串前缀中出现的位置信息；所述好字符数组GC与模式串长度一致。3.根据权利要求1所述的基于KMP匹配算法的字符串快速匹配方法，还包括如下：所述文本串进行全文扫描时分为末字符匹配和前缀匹配两部分，首先在index位置对模式串P最末字符x进行匹配；若失配，则直接取坏字符表值移动字符串在下一个位置进行比较；若同配，则匹配模式串前缀，若所述前缀也同配，则字符串找到；当所述前缀j位置失配，则求出由KMP算法模式值next决定的移动距离，再访问好字符数组GC，计算模式串P的最大移动距离。2CN110909214A说明书1/5页基于KMP匹配算法的字符串快速匹配方法技术领域[0001]本发明属于数据处理技术领域，特别是涉及一种基于KMP匹配算法的字符串快速匹配方法。背景技术[0002]字符串匹配阵是数字处理过程中的基本问题，实际上是字符的模式匹配，即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配；所谓关键词匹配，是指给定一个长为n的文本串T[1，n]和长为m的模式串P[1，m]，找出文本串T中与模式串所有精确匹配的子串的起始位置。[0003]常见的字符匹配算法包括BF算法；BF算法思想是从文本串的第一个字符开始和模式串进行匹配；若匹配成功，则继续比较后面的字符；否则文本串指针回溯到后一个位置从第二个字符开始和模式串第一个字符进行匹配。依此下去，直到和模式串匹配成功或到文本串的末尾为止。它的时间复杂度一般情况下为O((n-m+1)m)其中：n和m分别为主串和模式串的长度，最坏的情况下为O(m*n)，最好的情况下为O(m+n)；基于BF算法的时间复杂度明显较高，字符匹配效率较低。[0004]KMP模式匹配算法针对BF算法做了改进；其基本思想是：设计一个与模式串本身局部匹配信息构造的模式值数组next，当匹配过程中出现失配时，利用模式值将模式串向右“滑动”尽可能远的一段距离了，从而跳过一些不必要的比较以提高模式匹配的效率。例如：对给出的的文本串T[0，n-1]与模式串P[0，m-1]，假设在模式匹配的进程中，执行T[i]和P[j]的匹配检查；若T[i]＝P[j]，则继续检查T[i+1]和P[j+1]是否匹配；若T[i]≠P[j]，则分成两种情况：若j＝0，则模式串右移一位，检查T[i+1]和P[0]是否匹配；若1≤j<m，则模式串右移j-next(j)位，检查T[i]和P[next(j)]是否匹配。重复此过程直到j＝m-1或i＝n-1结束；该算法的时间复杂度为O(m+n)。[0005]而