从品牌网站建设到网络营销策划,从策略到执行的一站式服务
这篇文章主要介绍“C语言中怎么实现朴素模式匹配算法”,在日常操作中,相信很多人在C语言中怎么实现朴素模式匹配算法问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C语言中怎么实现朴素模式匹配算法”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
创新互联网站设计,为客户量身定制各类网站建设业务,包括企业型、电子商务型、成都响应式网站建设、行业门户型等各类网站,实战经验丰富,成功案例众多。以客户利益为出发点,创新互联网站制作为客户规划、按需搭建网站符合企业需求、带有营销价值的网络建站方案认真对待每一个客户,我们不用口头的语言来吹擂我们的优秀,近千家的成功案例见证着我们的成长。字符串模式匹配:在主串中找到与模式串相同的子串,并返回其所在位置。
注意:
①、子串——主串的一部分,一定存在。
②、模式串——不一定能在主串中找到
主串长度为n,模式串长度为m。
朴素模式匹配算法:将主串中所有长度为m的子串依次与模式串匹配对比,直到找到一个完全匹配的子串,或所有的子串都不匹配为止。
最多对比n-m+1个子串
(一)通过数组下标实现朴素模式匹配算法
若当前⼦串匹配失败,则主串指针 i 指向下⼀个⼦串的第⼀个位置,模式串指针 j 回到模式串的第⼀个位置
若 j > T.length
,则当前⼦串匹配成功,返回当前⼦串第⼀个字符的位置 —— i - T.length
int Index(SString S, SString T){ int i=1,j=1; while(i <= S.length && j<=T.length){ if(S.ch[i]==T.ch[j]){ ++i; ++j; //继续比较后继字符 } else{ i=i-j+2; j=1; //指针后退重新开始匹配 } } if(j > T.length) return i-T.length; else return 0; }
(二)时间复杂度
设主串⻓度为 n,模式串⻓度为 m,则
①、最坏时间复杂度 = O(nm)
②、好时间复杂度 = O(n) 1. 最坏时间复杂度O(nm)
最坏的情况,每个⼦串都要对⽐ m 个字符,共 n-m+1 个⼦串,复杂度 = O((n-m+1)m) = O(nm)
注:很多时候,n >> m
2. 好时间复杂度O(n)
好的情况,每个⼦串的第⼀个字符就匹配失败,共 n-m+1 个⼦串,复杂度 = O(n-m+1) = O(n)
注:很多时候,n >> m
到此,关于“C语言中怎么实现朴素模式匹配算法”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图