算法（2）KMP算法
1.0 问题描述
实现KMP算法查找字符串。
2.0 问题分析
- “KMP算法”是对字符串查找“简单算法”的优化。
- 字符串查找“简单算法”是源字符串每个字符分别使用匹配串进行匹配，一旦失配，模式串下标归0，源字符串下标加1。
- 可以很容易计算字符串查找“简单算法”的时间复杂度为O（m*n），其中n表示源字符串长度，m表示匹配串长度。
- KMP算法的匹配方式同简单算法的匹配方式相同，只不过在失配的时候，模式串下标不归零，反而会根据模式串自身的重复信息，回归到一个大于0的下标。从而减少匹配次数。
- 那么失配时候，模式串下标回归的位置需要提前计算好。计算的方法是，匹配串中，每个位置的前缀字符串“头部”和“尾部”的重复字符数即为失配下标回归位置。
- 假设匹配串是：ababc
- 下标0的字符是“a”，它的前缀是空字符串，所以回归位置为0
- 下标1的字符是“b”，它的前缀是“a”，数量不足2个，回归位置也是0
- 下标2的字符是“a”，他的前缀是“ab”，没有重复的头部和尾部，回归位置是0
- 下标3的字符是“b”，它的前缀是“aba”，有重复的头部和尾部，重复子串是“a”，长度为1，回归位置是1
- 下标3的字符是“c”，它的前缀是“abab”，有重复的头部和尾部，重复子串是“ab”，长度为2，回归位置是2
- 根据上一条，我们可以计算出一个next数组用于保存失配时模式串下标应该回到哪里的下标序列。
- 计算好next数组后，就可以使用“简单算法”的逻辑进行匹配了，只不过不同的是，一旦失配，匹配串下标不是回归到0，而是根据next数组决定。
3.0 代码实现
3.1使用swift实现
///简单查找
func simpleSearch(_ src: String, _ mode: String, _ start: Int) -> Int {var i = start;while i < src.count {var j = 0;while j < mode.count {if(i + j >= src.count || src[i + j] != mode[j]){break;}j += 1;}if j == mode.count{return i;}i += 1;}return -1;
}///kmp字符串查找
func kmpSearch(_ src: String, _ mode: String, _ start: Int) -> Int {//计算nextvar next: [Int] = [0, 0];//自身匹配，i表示主下标，j表示匹配下标var i = 2, j = 0;while i < mode.count {if(mode[i - 1] == mode[j]){next[i] = j + 1;i += 1;j += 1;}else{if(j == 0){i += 1;}//已经匹配的部分有可能会有首尾相同的情况j = next[j];}}//算法同自身匹配i = start;j = 0;while i < src.count {if(src[i] == mode[j]){i += 1;j += 1;if(j == mode.count){return i - mode.count;}}else{if(j == 0){i += 1;}j = next[j];}}return -1;
}
3.2使用js实现
function simpleSearch(src, mode, start){for(let i = start; i < src.length; i++){let miss = false;for(let j = 0; j < mode.length; j++){if(i + j >= src.length){miss = true;break;}else if(src.charAt(i + j) != mode.charAt(j)){miss = true;break;}}if(!miss){return i;}}return -1;
}function kmpSearch(src, mode, start){let next = [0, 0];let i = 2; let j = 0;while (i < mode.length) {if(mode.charAt(i - 1) == mode.charAt(j)){j++;i++;next[i-1] = j;}else{if(j == 0){i++;}j = next[j];}}i = start;j = 0;let found = false;while (i <= src.length) {if(src.charAt(i) == mode.charAt(j)){i++;j++;if(j == mode.length){found = true;break;}}else{if(j == 0){i++;}j = next[j];}}if(found){return i - mode.length;}else{return -1;}
}
4.0 复杂度分析
- 我们选取复杂度最大的一种模型来分析，即：模式串所有字符都相同，源串和模式串总是在最后一位失配。
- 令源串为 “aaaabaaaabaaaab”，匹配串为 “aaaaa”。
- 匹配串的next数组为：[0,0,1,2,3]
- 首次匹配会在第5位失配，比较次数为5。
- 模式串回到3，进行一次比较即会失配，比较次数为1。
- 模式串回到1，进行一次比较即会失配，比较次数为1。
- 模式串回到0，同时源串下标加1。此时源串下标为6，匹配串下标为0。根据源串特点，此时会不断重复4-7的过程。
- 根据上述分析，我们推到一般情况，长度为n的源串，长度为m的匹配串，会形成一个周期性匹配，周期次数为n/m。
- 很容易看到一个周期内的复杂度小于O(2m)，所以整体复杂度小于 O(2m*n/m)=O(2n)，即复杂度为O(n)。
- 计算next数组的算法和匹配算法相同，因此复杂度为O(m)。
- 所以KMP算法整体复杂度为O(m+n)。
相关文章：
告别无止境的增删改查：Java代码生成器
对于一个比较大的业务系统，我们总是无止境的增加，删除，修改，粘贴，复制，想想总让人产生一种抗拒的心里。那有什么办法可以在正常的开发进度下自动生成一些类，配置文件，或者接口呢&…
Maven国内源设置 - OSChina国内源失效了，别更新了
Maven国内源设置 - OSChina国内源失效了，别更新了 原文：http://blog.csdn.net/chwshuang/article/details/52198932 最近在写一个Spring4.x SpringMVCMybatis零配置的文章，使用的源配的是公司的私有仓库，但是为了让其他人能够通过…
如何使用Next.js创建动态的Rick and Morty Wiki Web App
Building web apps with dynamic APIs and server side rendering are a way to give people a great experience both with content and speed. How can we use Next.js to easily build those apps?使用动态API和服务器端渲染来构建Web应用程序是一种使人们在内容和速度上都…
安装部署Spark 1.x Standalone模式集群
Configuration spark-env.sh HADOOP_CONF_DIR/opt/data02/hadoop-2.6.0-cdh5.4.0/etc/hadoop JAVA_HOME/opt/modules/jdk1.7.0_67 SCALA_HOME/opt/modules/scala-2.10.4 ####################################################### #主节点 …
算法（3）简单四则运算
1.0 问题描述 实现10以内四则运算（只包含数字，*/和小括号） 2.0 问题分析 四则运算使用“后缀表达式”算法来计算，后缀表达式可以无需考虑运算符优先级，直接从左至右依次计算。问题分解成2部分，一是将“中…
调用短信接口,先var_dump()看数据类型是object需要json_decode(json_encode( $resp),true)转换成array...
返回的数据.先看类型,如果是object类型 先json_encode, 再json_decode,加true 转换成数组 $resp $c->execute($req); var_dump($resp); object(stdClass)#12 (2) { ["result"]> object(stdClass)#13 (3) { ["err_code"]> string(1) "0"…
nlp文本数据增强_如何使用Texthero为您的NLP项目准备基于文本的数据集
nlp文本数据增强Natural Language Processing (NLP) is one of the most important fields of study and research in today’s world. It has many applications in the business sector such as chatbots, sentiment analysis, and document classification.Preprocessing an…
R语言-基础解析
二、操作基础%%取余%/%整数除法(1)eigen(...)求解方阵的特征值和特征向量(2)solve(D,A)求解DXA(3)data<-list(...)取里面的对象data[["列名称"]]；data[[下标]]；data$列名称(4)unlist(列表对象)把列表对象转化为向量对象(5)names(数据框)读取…
算法（4）数据结构：堆
1.0 问题描述 实现数据结构：堆。 2.0 问题分析 堆一般使用数组来表示，其中某个节点下标i的两个子节点的下标为 2i1 和 2i2。堆是一棵完全二叉树。堆有3种基本操作：创建，插入，删除。这3种操作都需要通过“调整堆”的…
cookie 和session 的区别详解
转自 https://www.cnblogs.com/shiyangxt/archive/2008/10/07/1305506.html 这些都是基础知识，不过有必要做深入了解。先简单介绍一下。 二者的定义： 当你在浏览网站的时候，WEB 服务器会先送一小小资料放在你的计算机上，Cookie 会…
如何设置Java Spring Boot JWT授权和认证
In the past month, I had a chance to implement JWT auth for a side project. I have previously worked with JWT in Ruby on Rails, but this was my first time in Spring. 在过去的一个月中，我有机会为辅助项目实现JWT auth。 我以前曾在Ruby on Rails中使用…
算法（5）哈希表
1.0 问题描述 实现数据结构：哈希表。 2.0 问题分析 哈希表可以看作我们经常使用的字典（swift）或对象（js），可以让一个key&value对一一对应，可以快速根据key找到value。哈希表内部使用数组…
《面向对象程序设计》c++第五次作业___calculator plus plus
c第五次作业 Calculator plusplus 代码传送门 PS:这次作业仍然orz感谢一位同学与一位学长的windows帮助，同时再次吐槽作业对Mac系统用户的不友好。（没朋友千万别用Mac！！！） 还有想吐槽作业对规范的要求大大超…
联合体union和大小端（big-endian、little-endian）
1.联合体union的基本特性——和struct的同与不同union，中文名“联合体、共用体”，在某种程度上类似结构体struct的一种数据结构，共用体(union)和结构体(struct)同样可以包含很多种数据类型和变量。在成员完全相同的情况下，struct比…
前端面试的作品示例_如何回答任何技术面试问题-包括示例
前端面试的作品示例Technical interviews can be extremely daunting. From the beginning of each question to the end, its important to know what to expect, and to be aware of the areas you might be asked about. 技术面试可能会非常艰巨。 从每个问题的开始到结束&a…
$(shell expr $(MAKE_VERSION) \= 3.81) 这里“\”的解释
android/build/core/main.mk $(shell expr $(MAKE_VERSION) \> 3.81) 为什么要加多一个“\”,因为">"会被shell解析为重定向符号，所以需要转义或用引号包围 所以，也可以这样写$(shell expr $(MAKE_VERSION) “>” 3.81)转载于:https:…
iOS应用模块化的思考及落地方案（一）模块的划分及模块化工作流程
1.0 什么是模块化 很多关于重构及设计模式的介绍中，经常提到的几个词语是复用及解耦。 模块化之所以被提出，也更多是为了解决这几个问题。 复用可以减少重复造轮子的情况，很容易理解的是，我们经常使用的github上的第三方框架&a…
Swiper 用法
部分常用API ininialSlide: 2, //起始图片切换的索引位置（起始从0开始，默认为0） autoplay: 3000, //设置自动切换时间，单位毫秒 speed: 1000, //设置滑动速度 continuous: true, //无限循环的图片切换效果 disableScroll: true, /…
node/js 漏洞_6个可用于检查Node.js中漏洞的工具
node/js 漏洞Vulnerabilities can exist in all products. The larger your software grows, the greater the potential for vulnerabilities. 所有产品中都可能存在漏洞。 您的软件增长得越大，潜在的漏洞就越大。 Vulnerabilities create opportunities for expl…
发现一个浏览器很奇怪的问题
浏览器有8个请求状态为pending时，在另一个tab中，请求就发布出去了，一直是stalled。直到pending状态变成了cancled状态。 试了360浏览器（谷歌内核）和chrome浏览器，都是这样。 具体的原因待深究 参考…
wamp配置虚拟主机
因为wampserver的php版本一直是5.x版本；因此转投xmapp用了一段时间； 意外发现wampserver3更新了；php也终于更新到7了； 果断还是决定回到wampserver的怀抱； 然后有意外的发现了wampserver3有了新功能；可以方…
iOS应用模块化的思考及落地方案（二）模块化自动构建工具的使用
1.0 iOS模块化中的问题 前文已经介绍了模块化的流程及一些常见的问题，我们在这里再次总结一下。 在工作中，当我们开始一个新项目的时候，最先考虑的就是模块化工作。 模块化工作的想法是很美好的，可是执行过程中会遇到很多的问题…
aws fargate_我如何在AWS Fargate上部署＃100DaysOfCloud Twitter Bot
aws fargateAfter passing my last certification, I asked myself how much time I spent studying cloud computing.通过上一份认证后，我问自己自己花了多少时间研究云计算。 More than 100 days!超过100天！ It also made me realize two things:这也…
think in Java 第五章之垃圾回收类型
1.引用计数： 每个对象都含有一个引用计数器，当有引用连接至对象时，引用计数加1，当引用离开作用域或被置为null时，引用计数减1. 缺陷：在对象循环引用时，存在“对象应该被回收，引用计数…
Yii 错误页面处理
【错误页面处理】 訪问一个错误的控制器 訪问一个错误的方法 有些控制器和方法禁止訪问 以上訪问会提示错误信息 404 403 以上错误信息是不方便给外边用户看到的。 1. 安全隐患 2. 用户体验不好 错误信息在site/error这个地方定义的。如今我们要自己定义错误页面来显示我们的错…
设置RGBColor
#define kUIColorFromRGB(rgbValue) [UIColor \colorWithRed:((float)((rgbValue & 0xFF0000) >> 16))/255.0 \green:((float)((rgbValue & 0xFF00) >> 8))/255.0 \blue:((float)(rgbValue & 0xFF))/255.0 alpha:1.0]
自学成才翁_作为一名自学成才的开发者从“我的旅程”中吸取的教训
自学成才翁The path of the self-taught developer is tough and filled with uncertainty. There is no straight line from newbie to career programmer. Because of this, I believe all self-taught developers have a unique story to tell.自学成才的开发者之路艰难而充…
67）vector的begin（） end（） 和 front（） back（）的区别 rbegin（） rend（）
1） 2）v1.begin() 和v1.end（） 是作为迭代器v1的 第一个位置 和 最后一个元素的下一个位置。 v1.front() 是v1这个动态数组的第一个元素的值 v1.back()是v1的最后一个元素的值。 3） 4）正向和反向的使…
倒置函数reverse的用法
倒置字符串函数reverse：用于倒置字符串s中的各个字符的位置，如原来字符串中如果初始值为123456，则通过reverse函数可将其倒置为654321，程序如下：#include<stdio.h>#include<string.h>void reverse(char s[…
设置tabbaritem的title的颜色及按钮图片
设置title颜色： [[UITabBarItem appearance] setTitleTextAttributes:{NSForegroundColorAttributeName : kUIColorFromRGB(0xb2151c)} forState:UIControlStateSelected]; 设置按钮图片： UIImage *commonImage [UIImage imageNamed:[NSString strin…