当前位置: 首页 > news >正文

山东定制网站建设公司最新新闻事件

山东定制网站建设公司,最新新闻事件,邮箱格式怎么写,有什么比较好的做简历的网站朴素模式匹配算法最坏的情况: 一.实例: 第一轮匹配失败,开始下一轮的匹配: 不断的操作,最终匹配成功: 如上述图片所述,朴素模式匹配算法会导致时间开销增加, 优化思路:主…

朴素模式匹配算法最坏的情况:


一.实例:

第一轮匹配失败,开始下一轮的匹配:

不断的操作,最终匹配成功:

如上述图片所述,朴素模式匹配算法会导致时间开销增加,

优化思路:主串指针不回溯,只有模式串指针回溯

主串指针不回溯:

如果上述图中?是g:

如果上述图中?不是g:

另一种情况如下:

如果在j为5时匹配失败(j为模式串的指针),那么主串中分别以第5个字符即g,第6个字符即o,第7个字符即o开头的子串都不可能与模式串匹配,但第8个字符即g开头的子串有可能与模式串匹配成功,因为第8个字符即g能与模式串第一个字符g匹配上,而且在匹配过程中只是说明了子串中第9个字符与模式串中j为5时对应的字符不匹配,并没有说明子串中第9个字符与模式串中第二个字符不匹配,接下来只需要看i对应的字符即第9个字符是否与模式串中第二个字符即o是否匹配

再下一种情况:

如果在j为4时匹配失败(j为模式串的指针),那么主串中分别以第3个字符即g,第4个字符即o,第5个字符即o开头的子串都不可能与模式串匹配,此时就需要开始判断主串中第6个字符是否与模式串中第一个字符是否匹配,但其实j为4时匹配失败已经说明主串中第6个字符不是g了,因此主串中第6个字符已经不可能与模式串中第一个字符匹配,可知该方案并不是最优解,这种方案会使得多进行一次不必要的判断,但相比朴素模式已经优化了很多:

再再下一种情况:

如果在j为3时匹配失败(j为模式串的指针),那么主串中以第四个字符即o开头的子串一定与模式串匹配失败,但此时只知道主串中第五个字符不是o,因此可以判断主串中第五个字符是否是g,以主串中第五个字符开头来重新开始与模式串的匹配,相比朴素算法也优化了很多:

再再再下一种情况:

如果在j为2时匹配失败(j为模式串的指针),那么主串中以第三个字符即g开头的子串一定与模式串匹配失败:

汇总:

对于next数组,该数组的意思是当模式串的指针j等于next数组中的某一个值时,如果发生不匹配,如j为5时不匹配,就要回到j为2这个位置;

但当j为1时发生了不匹配,j设置为0:

代码:

形参中S为主串,T为模式串,还有与T对应的next数组,i指向主串,j指向模拟串,while循环中j不为0且i指向的字符和j指向的字符不相等时才执行else语句里的j=next[j]:

与朴素算法不同的有第一个if语句中j==0和第一个else语句中的j=next[j],

现在假设主串为xgoo,模式串为google,一开始j为1,指向模拟穿里的g,i为1,指向主串里的x,

由于i和j指向的字符不匹配(不相等),根据j=next[j],会让j=next[1],此时j为0,下一轮循环时发现j为0,

++i后i为2指向主串里的g,++j后j为1指向模拟串里的g,由此就推出为什么把next[1]设为0,因为可以利用这个信息做一个特殊的判断,当j为0时就说明主串的指针i也应该往右移动了,此外当i指向的字符和j指向的字符都相等时也应该把i和j同时往后移:


http://www.tj-hxxt.cn/news/40994.html

相关文章:

  • 有什么那个网站网络推广的基本方法有哪些
  • 高端设计网站平台网站推广关键词工具
  • 旅游网站制作分析广点通
  • 商务网站建设与维护实训报告青岛百度推广优化
  • 做一个跨境电商网站无锡优化网站排名
  • 云服务器可以做图片外链网站吗中国十大新闻网站排名
  • 政府网站风格磁力bt种子搜索神器
  • 网络广告推广员爱站seo查询
  • 网站被主流搜索引擎收录的网页数量网络推广经验
  • 网上做网页网站任务赚钱福州百度seo代理
  • 网站 通管局 报备营销知识和技巧
  • mysql asp网站给你一个网站seo如何做
  • 有什么网站可以做婚庆视频湖南 seo
  • 虹口网站建设公司搜索引擎官网
  • 青岛做网站找什么公司免费网站建设seo
  • 电子商务及网站建设seo优化的方法有哪些
  • 小区网站建设刷推广链接
  • 网站建设报价单及项目收费明细表鄂尔多斯seo
  • 做网站要用写接口6企业seo顾问
  • asp+php+mysql+aspx环境搭建与6种网站安装2青岛做网站推广公司
  • 洪梅镇做网站周口seo公司
  • 网站开发数据库技术毕业论文十堰seo排名公司
  • 网站编辑的工作内容网站优化排名优化
  • 南京专业网站制作公司购买链接平台
  • 上海交通大学文科建设处网站百度seo视频教程
  • 网站的备案流程图推广软件赚钱的app
  • 网站后门清除网址seo分析
  • 福田做棋牌网站建设多少钱2345浏览器导航页
  • 湖北 网站 备案 时间电脑零基础培训班
  • asp语言网站建设网络工程师