KMP算法是字符串匹配问题中非常经典的算法。最近查找了很多相关资料，直到看到下面这两篇博客，终于理解了KMP的基本原理。
KMP算法的核心即是计算字符串M每一个位置之前的字符串的前缀和后缀公共部分的最大长度。获得M每一个位置的最大公共长度之后，就可以利用该最大公共长度快速和字符串S比较。当每次比较到两个字符串的字符不同时，我们就可以根据最大公共长度将字符串M向右移动，接着继续比较下一个位置。
强烈推荐大家看一看以下两篇博客，相信能有所收获。
首先推荐看这篇，篇幅较短，没有大量的算法细节，建议先读这篇，对KMP算法的核心思想有所把握：
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
在了解基本思想后，建议详细阅读下面这位大神的博客，写的非常清晰，认真研读之后，相信会对KMP有深入的了解，并能编程实现。
https://blog.csdn.net/v_july_v/article/details/7041827
在网上没有查到比较清晰的python解决方案，在这里给出python实现方法，
供参考。（笔者测试了多个测试用例，均通过，如有问题，欢迎指出~）
搜索字符串S中是否含有模式串P，如果有，返回True，否则返回False
def KMP(S,P):
def next_list_generate(s):
'''
产生模式串的next列表，此处为KMP核心部分，强烈建议大家仔细阅读 上面的两篇博客
'''
if len(s) == 0 :
return False
if len(s) == 1:
return [-1]
if len(s) == 2:
return [-1,0]
next_list = [0]*len(s)
next_list[0]= -1
flag = 2
k = 0
while flag < len(s):
if k == -1 or s[k]==s[flag-1]:
k += 1
next_list[flag] = k
flag += 1
else:
k = next_list[k]
return next_list
if len(S)<len(P):
return False
next_list = next_list_generate(P)
match = 0
flag = 0
while flag+len(P)<=len(S) :
for i in range(len(P)):
if P[i] == S[flag+i]:
match += 1
else:
flag += match - next_list[i]
break
if match == len(P):
return True
match = 0
return False
测试样例：
#instance1
Str = 'freerh'
Pattern = 'erh'
print KMP(Str,Pattern)
#instance2
Str = 'abcd'
Pattern = 'be'
print KMP(Str,Pattern)
#instance3
Str = 'abcdf'
Pattern = 'bcdg'
print KMP(Str,Pattern)
测试输出：
True
False
False
def KMP_search(text:str,pattern:str)->bool:
if len(pattern)>len(text) or len(pattern)==0:
return False
def get_next(pattern):
next_list=[0 for i in range(len(pattern))]
next_list[0]=-1
i=-1
j=0
while(j<len(pattern)-1):
if(i==-1 or pattern[i]==pattern[j]):
i+=1
j+=1
next_list[j]=i
else:
i=next_list[i]
return next_list
next_list=get_next(pattern)
ti=0
pi=0
while ti<len(text):
if text[ti]==pattern[pi]:
if pi==len(pattern)-1:
return True
else:
ti+=1
pi+=1
elif pi==0:
ti+=1
else:
pi=next_list[pi]
return False
测试输入:
print(KMP_search('b','b'))
print(KMP_search('bsdfss','bsdfss'))
print(KMP_search('bsdfsa','sa'))
print(KMP_search('b','a'))
print(KMP_search('bsdfsa','ssa'))
print(KMP_search('bsdfsa','bsdfsb'))
测试输出:
True
True
True
False
False
False
文章浏览阅读1w次。由于项目需要对照片的EXIF信息进行处理，因此在网上搜索了一番。捣鼓出来了，写下，总结。需要用到2个jar包，metadata-extractor-2.3.1和mediautil-1.0。这2个jar包比较好找，地址就不写了，搜索下就OK。需要注意的是，mediautil-1.0这个jar包你需要修改下。因为，项目需要修改GPS，其提供的例子后面还提供了个地址，里面有5个java文件，拿出来，_tinyexif 移植到java项目中
文章浏览阅读5.1w次，点赞137次，收藏1.1k次。前言这篇文章是我学习esp8266的一些学习方法与笔记，记录下来方便以后开发深入学习，也希望各位学者通过这篇文章找到自己的学习esp8266的方法，以免走更多弯路。对esp8266我也是初学者，希望各位物联网大佬多多指点。以下是我学习的一些方法以及资料。希望能带给你帮助。一、视频学习我在B站找到一个比较好学习正点原子模块ATK-ESP8266的视频，推荐给大家观看，老师很有趣，看完你就会对这个模块有全新的理解视频链接：https://www.bilibili.com/video/BV1wV411_正点原子esp8266
文章浏览阅读1.7k次。一、vuex简介vuex 是一个专为 Vue.js 应用程序开发的状态管理模式 + 库。它采用集中式存储管理应用的所有组件的状态，并以相应的规则保证状态以一种可预测的方式发生变化。vuex可以作为一种插件，可以将数据，同步异步的方法统一管理，vuex这个整体是一个仓库，用store来指定，这个仓库包含了数据和方法，仓库内部分为了三个区域actions是存放异步方法并且调用的地方mutations是存放同步调用方法的地方并且将数据传给statestate，状态，是存放数据处二、_前端vuex的知识点
文章浏览阅读2.6k次。摘要：LeNet-5是Yann LeCun在1998年设计的用于手写数字识别的卷积神经网络，当年美国大多数银行就是用它来识别支票上面的手写数字的，它是早期卷积神经网络中最有代表性的实验系统之一。可以说，LeNet-5就相当于编程语言入门中的“Hello world！”。华为的昇腾训练芯片一直是大家所期待的，目前已经开始提供公测，如何在昇腾训练芯片上运行一个训练任务，这是目前很多人都在采坑过程中，所以我写了一篇指导文章，附带上所有相关源代码。注意，本文并没有包含环境的安装，请查看另外相关文档。环境约束_华为云卷积神经网络如何使用npu
文章浏览阅读664次。vuecli3实现全局公用弹窗实现功能：用户登录的时候，根据轮班设置会产生一个用户的轮班结束时间，就是下线时间，到了时间点要弹窗提示用户轮班时间到了，如果不操作倒计时五分钟自动注销，如果点击继续值班，每十分钟再弹窗提醒用户登录后 不管用户在操作哪一个页面 ,到达轮班时间点 ,都显示"轮班时间已到"提示框 ,提示用户进行下一步的操作, 用vuex管理全局弹窗框的显隐效果图：1、首先定义好一..._vue3定时退出
文章浏览阅读3.8k次，点赞3次，收藏8次。多数据源下，多模块依赖mybatis扫描不到xml文件，调用mapper接口出现org.apache.ibatis.binding.BindingException问题###前置说明handler 项目有三个数据库master、second、thirdhandler项目中新增引用common模块的model和dao <dependencies> <dependency> <groupId>cn.wxt.common&l_数据源切换后找不到mapper文件
文章浏览阅读2.7k次，点赞2次，收藏17次。【代码】1、编写Java程序，在屏幕上输入一个四位整数，依次输出其每位数字的值，并输出其逆序数。_编写程序求一个四位数并输出
文章浏览阅读1.9k次。一个比较简单大方的插件ChatGPT-Next-Webgithub上4.3k的加星量的项目_chatgpt-next-web
文章浏览阅读1.3k次。我们知道徐雪力老师的xxl-job定时调度任务是可以解决集群情况下的调度重复问题的...内置了轮询,单一,随机,hash等算法来实现单个机器执行定时 的需求.但是我们项目因为是多环境的....而每一个执行器都有他自己的执行器Appname,所以如果一个项目中的定时任务执行器名称就设置一个的话,回到多环境情况下使用的是同一个执行器名称.也就会造成注册的ip地址是多个环境的机器的ip.此时再进行轮询就会造成该定时任务轮询到了不同机器上面.为了解决这个问题有两种方案:方..._xxl-job 如何区分生产 测试
文章浏览阅读1.2k次，点赞3次，收藏2次。导读：作者有幸在中国电子信息领域的排头兵院校“电子科技大学”攻读研究生期间，接触到前沿的数字IC验证知识，旁听到诸如华为海思、清华紫光、联发科技等业界顶尖集成电路相关企业面授课程，对数字IC验证有了一些知识积累和学习心得。为帮助想入门前端IC验证的朋友，思忱一二后，特开此专栏，以期花最短的时间，走最少的弯路，学最多的IC验证技术知识。文章目录一、内容概述二、面向对象编程（OOP）2.1、为什么要使用面向对象编程的方法？2.2、面向对象的基本概念一、内容概述面向对象编程（OOP）面向对象编程的基._ic验证语法
文章浏览阅读1.7w次，点赞10次，收藏25次。Unity资源检测工具AssetChecker的优势支持所有版本的Unity项目不依赖Unity Editor，无需安装绿色运行检测速度极快，可在UPR中查看检测结果和修改建议支持命令行模式，可以CI/CD工具轻松集成，实现自动化检测检测库持续更新支持AssetBundle冗余检测支持静态代码分析请到UPR官网下载最新版资源检测工具，下载地址：AssetChecker-Win使用流程注意：下载包的exe文件不是直接双击运行的，它是个命令行工具，得在cmd里使用。按住Win_upr静态资源监测
文章浏览阅读780次。There’s a dirty secret about creating queues and exchanges in Rabbit: by default they don’t survive reboot. That’s right; restart your RabbitMQ server and watch those queues and exchanges go poof (alo