朴素的模式匹配算法

朴素的模式匹配算法朴素的模式匹配算法东北石油大学计算机与信息技术学院李勇勇朴素的模式匹配算法算法思路:对于主串的每一个字符作为子串的开头，与要匹配的字符串进行匹配，对主串做最大的循环，每个字符开头都做子串长度的小循环，知道匹配成功或者全部遍历完成为止。 /*返回子串T在主串S中第pos个字符之后的位置，若不存在，额函数返回值为0，若T非空，1 T[0]) return i - T[0]; else return 0; } 最好的情况下时间复杂度是O(1) 一般的情况下时间复杂度是O(n+m) 最坏的...

朴素的模式匹配算法东北石油大学计算机与信息技术学院李勇勇朴素的模式匹配算法算法思路:对于主串的每一个字符作为子串的开头，与要匹配的字符串进行匹配，对主串做最大的循环，每个字符开头都做子串长度的小循环，知道匹配成功或者全部遍历完成为止。 /*返回子串T在主串S中第pos个字符之后的位置，若不存在，额函数返回值为0，若T非空，1<=pos<=StrLength(S)*/ int Index(String S,String T,int pos) { int i = pos;//i用于主串S中当前位置下标，若pos不为1，则从pos位置开始匹配 int j = 1;//j用于子串T中当前位置的下标值 while(i<=S[0]&&j<=T[0]) { //若i小于S长度并且j小于T的长度时循环 if(S[i]==S[j]) { //如果两个字母相等，则继续 ++i; ++j; } else{ //指针后退重新开始匹配 //i退回到首次匹配的下一位 i = i - j + 2; j = 1;//j退回到子串T的首位 } } if(j > T[0]) return i - T[0]; else return 0; } 最好的情况下时间复杂度是O(1) 一般的情况下时间复杂度是O(n+m) 最坏的情况下时间复杂度是O((n-m+1)*m) 1

                    本文档为【朴素的模式匹配算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

你可能还喜欢

最新资料

资料动态

专题动态

is_954223

暂无简介~

格式：doc

大小：12KB

软件：Word

页数：2

分类：互联网

上传时间：2018-02-02

浏览量：12

热点搜索

暂列金额确认表联想法记单词大全(手工整理) DNV规范目录 03审计程序01一般审计程序04损益类PL02-其他业务收入常用热分析技术：差示扫描量热法(DSC)、差热分析(DTA)、热重分析(TAG) 袋装水泥使用许可申请详细说明征文演讲比赛巨人的脚步报价单木门企业污水处理设施有限空间作业安全自查检查表华中科技高数期末试题1 新冠疫情防控宣传课件坚决制止刑讯逼供教育整治活动心得体会数据中心机房人员出入登记表六年级数学下册简便计算暂列金额确认表联想法记单词大全(手工整理) DNV规范目录 03审计程序01一般审计程序04损益类PL02-其他业务收入常用热分析技术：差示扫描量热法(DSC)、差热分析(DTA)、热重分析(TAG) 袋装水泥使用许可申请详细说明征文演讲比赛巨人的脚步报价单木门企业污水处理设施有限空间作业安全自查检查表华中科技高数期末试题1 新冠疫情防控宣传课件坚决制止刑讯逼供教育整治活动心得体会数据中心机房人员出入登记表六年级数学下册简便计算