模式匹配BF算法分析及实现

任宪臻 任美玲

(1.北京信息职业技术学院 软件与信息学院，北京 100018;2.烟台南山学院 工学院计算机系，山东 烟台 265700)

字符串是以字符作为数据元素的线性表，是非常重要的非数值处理对象。目前大量地处理非数值计算问题都给通过计算机来实现，例如，文字编辑、信息检索、词法扫描、符号处理、自然语言翻译等。在事务处理程序中，如客户信息、货物产地等一般也都是作为字符串处理，因此字符串在很多领域都得到了广泛应用。字符串的逻辑结构与线性表的逻辑结构相同，但是它的基本操作却和线性表的基本操作有着很大的差别。线性表的基本操作主要是以“单个数据元素”作为操作对象，比如在线性表中的某个位置插入或删除一个元素、在线性表中按位查找或者按值查找某个元素等；而字符串的基本操作的操作对象却通常是一个“字符串整体”，比如在字符串的某个位置插入或者删除一个子串、在字符串中定位查找某个子串等。

字符串被广泛应用在非数值处理领域，其中字符串的查找定位操作是最经常用到的。字符串的查找定位也经常被称为字符串的模式匹配，是指在主串中寻找子串的一个过程。例如，如果给定两个字符串：S=“s1s2…sn”，T=“t1t2…tm”（1 ≤m ≤n），在主串S 中寻找子串T 的过程就称为模式匹配，其中字符串T 称为模式。如果在主串S 中找到了一个和模式T 相同的字符子串，则表示在主串S 中查找模式T 成功，也称模式T 匹配成功。当模式T 匹配成功时，返回模式T 的首字符在主串S 中的位置（本文设定字符的位置序号从1 开始计数）；……