当前位置:首页 >> 信息与通信 >>

BF与KMP模式匹配算法的实现与应用


实用第   智慧 密集   B F与 K MP模 式匹配算法的实现 与应用  明延 堂  摘  要 :从 数据 结构 的 角度 深入 浅 出地描 述 了 B F和 K MP两种 经典 的模 式 匹配算 法原理 ,并对 算  法的 时空 效率进 行 了分析 ;从编 程技 术 的 角度 使 用 J a v a 语 言 完整地 实现 了这些 算 法 :从 实 际应 用  出发 ,设

计 了一个 关 于模 式 匹配的 GUI 应用程序 。   关键词 :模 式 匹配 ; 目标 串;模 式 串;B F算 法 ;KMP算 法  1  B r u t e — F o r c e算 法  1 . 1   算 法描 述  B r u t e — F o r c e   f B F )算 法 是 一 种 简 单 的字 符 串模 式 匹 配算 法 。   假 设 目标 串 和 模 式 串 分 别 为 t a r g e t = t  ̄ t 1 …t   ,p a t t e r n = p  l …   P   ,0 < m≤n 。B F算 法 每 次 匹配 都 将 目标 串从 t   ( 0 ≤i ≤n — m )   串是 t  ̄ _ j t  1 . . ? t   ,则下 次 待 匹配 的字 串是 £  1 t   ? t I + 1 ,即下 次 比   较字符分别是 t   与P 。 , 目标 串 当 前 字 符 下 标 i 将 退 回到  +   1 ,模 式 串 当前 下 标 J 将 退 回到 0 。 如 果 目标 串 中 当前 字 串 与模  式 串 的 所 有 字 符 均 相 等 ,则 ≠m,表 示 匹 配 成 功 , 返 回 匹 配  子 串 的序 号 。   B F算 法 易 于 理 解 ,但 时 间效 率不 高 。 B F模 式 匹 配 的 时 间  代 价 主要 用 于 比较字 符 。   开 始 、长 度 为 m 的 子 串  一 t i 一。 与 模 式 串 比较 。 如 果 相 等 ,   则 匹 配成 功 ;否 则 本 次 匹配 失败 ,继 续 比较 目标 串 的下 一个 子  最好 情 况 是 ,第 一次  配 即成 功 ,模 式 串刚 好 与 目标 串 的   … 串t i + l t  一 t i   。 每 次 匹 配 过 程 中 , 比较 次 数 最 多 为 m 次 。在 模  式 匹 配 失败 时 , 目标 串 中参 与 匹 配 的字 串依 次 为  …t   ,t , t 2   … t   字 串匹 配 ,此 时 比较 次数 为模 式 串 长 度 m,时 间 复 杂  度为 0   f m ) 。如图 2   f a 】所示 。   最 坏 情 况 是 ,每 次 匹配 比较 m 次 ,匹 配 n — m + 1次 ,字 符  比较 总 次 数 是 m X( n — m+ 1 ) , 南于 m< n , 因此 时 问 复 杂 度 为 0   ( n X m ) 。对 于 t a r g e t = a a a a a 、p a t t e r n = a a b采 用 B F算 法 的 匹 配 过  程如图 2   f b )所 示 ,共 匹 配 4次 ,字 符 比较 l 1 次。   t   ,… ,f   一  …  …t … , 即 目标 串 中 所有 长 度 为 m 的 字 串都  与 模式 串 匹配 过 ,才 能保 证 不 丢 失 任 何 匹配 。   目标 串 和 模 式 串

相关文章:
基于BF和KMP的串模式匹配算法设计与实现(C语言)
int Index_KMP(SString S,SString T,int pos,int next[]) { /* 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后的位置的 KMP 算法。 ...
三种模式匹配算法的比较和分析
三种模式匹配算法的比较分析_IT/计算机_专业资料。东大 实验报告 随机算法三种模式匹配算法作业要求: 作业要求:分别用 KMP、MonteCarlo、LasVegs 算法编制三个程序...
文学研究助手与模式匹配算法KMP
研究助手与模式匹配算法 KMP 摘要 本实践课题重在对文本的查询,在实际应用中有...-7- 北京理工大学珠海学院计算机学院课程设计 2.2 源程序代码实现 源程序代码 ...
使用KMP算法实现一个模式匹配
课 程 设 计 ——数据结构 设计题目:KMP 算法实现一个模式匹配 指导老师:徐浩 学生姓名: 孙文莉 班级 学号 :信 122 班:129084227 2014 年 6 月 16 日 一...
经典中英文模式匹配算法比较
本文分析了 KMP、BM、AC WM 四种经典模式匹配算法,并提出了 KMP 算法的一种改进策略。 在面临复杂数据难以管理新形势下,本文还介绍了一种大 规模图数据库上...
KMP模式匹配算法
KMP模式匹配算法_计算机软件及应用_IT/计算机_专业资料。1. KMP 算法是一种线性时间复杂度的字符串匹配算法,它是对 BF 算法(BruteForce,最基本的字符串匹配算法)...
文学研究助手与模式匹配算法KMP
11 文学研究助手与模式匹配算法 KMP 一、系统开发的背景文学研究人员需要统计某...运用 get_next()函数,该模块主要实现:求模式串 T 中的 next 函 数值并存入...
模式匹配KMP算法数据结构课设
模式匹配KMP算法数据结构课设_计算机软件及应用_IT/计算机_专业资料。课程设计 -...} //BF 算法,普通的模式匹配算法 int IndexBF(char S[MAXSTRLEN],char T[...
模式匹配中的KMP算法的实现
串匹配就是在主串中查找模式串的一个或所有出现。 串匹配从方式上可 分为精确匹配、模糊匹配、并行匹配等,著名的匹配算法BF 算法、KMP 算法、BM 算法 ...
数据结构 基于BF和KMP的串模式匹配算法设计与实现
数据结构 基于BF和KMP的模式匹配算法设计与实现_数学_自然科学_专业资料。基于BF和KMP的模式匹配算法设计与实现 实验④:基于 BF 和 KMP 的串模式匹配算法设计...
更多相关标签:
用kmp算法实现匹配 | kmp模式匹配算法 | kmp字符串匹配算法 | kmp匹配算法 | kmp模式匹配算法代码 | kmp算法匹配次数 | 字符串匹配的kmp算法 | kmp算法匹配过程 |