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

网站建设页面生成网站开发合同

网站建设页面生成,网站开发合同,网站全站搜索代码,it运维管理系统一、目的1.KMP应用场景:可以解决字符串匹配问题; 在一个串中查找是否出现过另一个串。2.KMP的经典思想就是:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。3.KMP算法关键在于&…

一、目的

1.KMP应用场景:可以解决字符串匹配问题; 在一个串中查找是否出现过另一个串。

2.KMP的经典思想就是:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。

3.KMP算法关键在于:在当前对文本串和模式串检索的过程中,若出现了不匹配,如何充分利用已经匹配的部分。

4.理解KMP需要搞懂的几个方面:

  • 什么是前缀表?为什么一定要用前缀表?如何计算前缀表

  • 前缀表与next数组关系?构造next数组的几种方法?

  • 如何使用next数组来做匹配

二、理解过程

1.例子:用模式串去匹配文本串

(1)暴力破解:O(m+n)

(2)KMP算法:先进行常规匹配,到b和f不相等时,会直接将f移动到b的位置来匹配(因为b前面的两个a已经匹配好了),直至匹配完成。

2.前缀表:用来回退的,它记录了模式串与主串(文本串)不匹配时,模式串应该从哪里开始重新匹配。

(1)学会找最长相等前后缀(关键!!)

(2)前缀:包含首字母,不包含尾字母的所有子串

eg.例子里的前缀有a,aa,aab,aaba,aabaa。 aabaaf就不是前缀即不可以包含尾字母

同理后缀:f.af.aaf.baaf.abaaf

(3)什么是最长相等前后缀?

答:前缀=后缀且最长

过程:找模式串的最长相等前后缀也就是前缀表,利用前缀找最长相等前后缀:

a 0 (a既是前缀又是后缀,所以为0)

aa 1 (前一个a是前缀,后一个a是后缀,且都是a,则长度为1)

aab 0 (前缀有a,aa,后缀有b,ab,整个来讲找的就是前缀的前缀,前缀的后缀)

aaba 1 (第一个a和b后的a相等)

aabaa 2 (第一个a和最后的a;前aa和后aa)

aabaaf 0

从而得到前缀表为:010120

从图中可知,从第一个a开始匹配,发现到模式串f时匹配不成功,随即立马找f之前的串即aabaa的最长相等前后缀,也就是2,所以就从模式串位置2即第三个数开始重新匹配.

3.next数组:可以理解就是前缀表,但next数组写法很多

(1)其他写法

原始 0 1 0 1 2 0

整体右移 -1 0 1 0 1 2

整体减1 -1 0 -1 0 1 -1

但这里还是用原始的进行操作和编码

4.代码实现(也就是找最长相等前后缀的过程):

步骤:(1)初始化next数组和变量(2)处理前后缀不同的情况(3)处理前后缀相同的情况

(4)更新next

i代表后缀末尾; j指向前缀末尾,也代表包括i之前的最长相等前后缀的长度; 下面是代码和运行过程图

代码是伪代码,不完整:

public void getnext(int[] next, String s){
// 初始化j next;
j = 0, next[0] = j,
for(i = 1; i<s.length();i++){// 注意i从1开始,这样才能和j比较//前后缀不相同:j 遇到冲突就回退;//用while而不是if原因在于若不匹配,一直往前退到0或匹配为止,是个连续的过程;//j>0因为j的起始位置为0,再回退就越界了;while(j > 0 && s[i]!=s[j] ){j = next[j-1];  }// 向前回溯,回溯前一位的next中的位置//前后缀相同  if(s[i]==s[j])   j++;  最长相等前后缀长度加1next[i] = j;  }//将j(前缀的长度)赋给next【i】,不管前后缀是否相同,都要存放

例题实现strStr() ①先对模式串进行kmp,得到next数组即前缀表

②将文本串和模式串进行匹配,使用next数组保存的最长相等前后缀辅助。

http://www.15wanjia.com/news/20864.html

相关文章:

  • 银川专业做网站百度百科查询
  • 交易平台网站建设品牌推广运营策划方案
  • 校园网站做等级保护推广优化网站
  • 深圳前十网站建设公司seo教学
  • 香港网站域名申请百度seo排名优
  • 郑州公司网站建设服务排名优化工具下载
  • asp网站怎么做404页面跳转seo具体seo怎么优化
  • 保山市城乡建设局网站百度24小时人工客服
  • seo优化排名教程百度技术网站排名优化首页
  • 有点子外包做网站会不会被盗窃上海seo排名
  • 手机网站淘宝客怎么做产品推销方案
  • 有没人做阿里巴巴网站维护的营销网络怎么写
  • 查询网站域名备案申请网址怎么申请的
  • 沈阳企业网站怎样制作关键词排名批量查询
  • 在线看视频网站怎么做免费大数据查询
  • 建站行业突破关于友谊的连接
  • 茶叶网站实际案例贵阳搜索引擎排名推广
  • 朝阳周边做网站的公司营销管理制度范本
  • 沈阳网站制作费用阿里巴巴国际站官网
  • 房屋设计师破解版seo外包公司兴田德润官方地址
  • 做网站公司在丹麦常用的搜索引擎有哪些
  • 设计模板免费网站软文投放平台有哪些
  • 网站设计部什么是搜索关键词
  • 汪峰做的音乐网站百度竞价排名危机事件
  • 东风地区网站建设价格低白杨seo课程
  • 贵阳做网站的公司好口碑关键词优化地址
  • 钱宝做任务的网站怎么下aso关键词搜索优化
  • 房产经纪人怎么做网站基本seo技术在线咨询
  • 网站推广策划方案范文注册公司网上申请入口
  • 北京市做网站浙江网站建设平台