字符串拆分算法——一种新的模式匹配算
法
宋广泽
青岛科技大学 信息科学技术学院，青岛
摘要：KM P 算法和 BM 算法是经典的模式匹配算法，然而本文提供了一个全新的思路来解
决模式匹配问题，从而形成了一种新的算法——字符串拆分法。其核心思路是将字符串中
所有的连续子片段都找出来并存放到一个新的线性结构中，通过对新线性结构的遍历并使
用 C 语言中的字符串比较函数 strcmp 来一一匹配。
关键词：模式匹配；字符串拆分法；模糊搜索；C 语言
中图分类号：TP391.1
String splitting algorithm:a New pattern matching algorithm
Song Guangze
School of Information Science & Technology,Qingdao University of Science &
Technology,Qingdao 266100,China
Abstract:KMP algorithm and BM algorithm are classic pattern matching algorithms. However, this
paper provides a new idea to solve the pattern matching problem, thus forming a new algorithm --
string splitting method. The core idea is to take all the contiguous subfragments of a string and put
them into a new linear structure, and match them one by one by traversing the new linear structure and
using STRCMP, the string comparison function in C.
Key words:Pattern matching; String splitting; Fuzzy search;The C language
1 引言
模式匹配算法可用于模糊搜索，本文所提到的模糊搜索是指输入不完整的关键词即可
查询到对应的全部准确结果。例如：输入“天”即可将所有姓名中带有“天”字的人搜索出来；
输入“0809”即可将所有 ID 中带有“0809”片段的人搜索出来。
这种模糊搜索技术被广泛应用于各大有查询功能的软件，为用户提供了极大的方便。
在众多的 QQ/微信好友中，输入想要查找的联系人的姓名的一部分即可查找到该联系人；
在 excel 中，即使只记住了查询对象的几个字，也能够通过查找功能查询到对应的对象；在
百度搜索中，更是可以通过用户输入的信息搜索到含有用户输入信息片段的网页或者文献
很是方便。
本文侧重模式匹配算法在模糊搜索中的应用，提出一种更容易理解的模式匹配算法—
—字符串拆分算法。
2 字符串拆分算法及其应用于模糊搜索功能的分析
在介绍算法前，先作以下的定义，文本串表示为 str=str[0,1,2,...,N1-1]，长度为 N1；模
评论10