JAVA字符串算法——KMP算法（java的kmp算法）
ztj100 2025-07-15 02:16 3 浏览 0 评论
KMP算法是对字符串匹配算法的一个重大改进 , 创造性的利用子串本身的特性 , 来改进算法的效率。
KMP算法的关键或则精华 , 就是在与 next[ ] 的计算。
假设存在主串 S 和 子串 T , 我们在某一趟匹配中 , 发现 T（k） != S（i+1）
那我们就得到了一个部分的匹配结果
即：T（1）……T（k-1） = S（i-k+1） …… S（i-1）
我们假设存在一个 j < k 使得： T（1）……T（j-1） = S（i-k+1）……S（i-k+j-1）
也就是说 T（1）……T（j-1） = T（k-j）……T（k-1）
所以这时我们就需要把子串向右移动 k-j 位 , 而如果 此时不存在这样的情况 , 也就是 j = 0 , 那么我们就需要向右移动 k 位
因此我们只需要求出子串中每个位置对应的 j 既可
这就是KMP算法的思想
因此next（） 函数的定义如下：
0 j = 1 时
next（）= max（ k / 1<=k
1 当不存在上面的K且T（1） != T（j）
0 当不存在上面的K且T（1） != T（i）
求next（） 函数的代码如下：
char s[100]; //被匹配字符串
char t[100]; //匹配字符串
int next[100]; //存储匹配串中每个字符应移的距离
int s_length , t_length;//被匹配串和匹配串的字符长度
void getnext（）
{
int i = 0, j =-1;
next[i] = -1;
while（i < t_length）
{
while（j >= 0 && t[i] != t[j]） j = next[j]; //和该字符前面的字符比较 , 看是否和前面的字符相同
i++; j++;
if（t[i] == t[j]） next[i] = next[j];//如果当前两字符相同 ,
else next[i] = j;
}
for（i = 0; i < t_length; i++）
printf（"%d\n" , next[i]）；
}
//向右滑动的距离为：j-next[j]
相关推荐
- Win10预览版10532已知问题汇总（微软win11正式版已知问题一览）
-
IT之家讯微软已向Insider用户推送了Win10预览版10532更新，本次更新对右键菜单、《Windows反馈》应用以及Edge浏览器进行了改进。除此之外还包含一些Bug，汇总如下，有意升级Wi...
- Gabe Aul正测试Win10 Mobile 10532，Insider用户还需等
-
IT之家讯本月中旬微软向Insider用户推送了Win10Mobile预览版10512，该版本修复了一些Bug，增强了系统稳定性，但依然存在一些问题。今天，微软Insider项目负责人GabeAu...
- 微软开始推送Win10预览版10532快速版更新
-
8月28日消息，刚才，微软推送了Win10Build10532快速版，修复了之前的Bug，并带来了三项改进。主要来说，这次的更新改进了右键菜单的UI，使其更具Modern风格（见上图）。此外，更新...
- Win10预览版10532更新内容大全（windows10更新预览版）
-
IT之家讯今天凌晨微软向Insider用户推送了Win10预览版10532快速版更新，本次更新主要带来了三处改进，汇总如下：o改进右键菜单，外观更加Modern。这是基于网友要求界面一致的反馈做出...
- 无法升级Win10预览版10532?也许Hyper-V在搞鬼
-
根据IT之家网友的反映，安装了微软虚拟机Hyper-V的Win10预览版用户无法成功升级Build10532版本，安装过程中会被要求回滚系统。很多朋友在尝试关闭虚拟机之后重启安装程序，结果仍然无法顺...
- Win10预览版10532界面兴起“酷黑”风潮
-
Win10预览版10532的界面改动还是较为明显的，主要体现在右键菜单上面。总体来看，该版本的右键菜单间距更宽，视觉上更大气，操作上更便于触控。具体来说，任务栏右键菜单的变化最为明显。除了增加选项的宽...
- Win10预览版10532上手图集（windows10预览版下载）
-
IT之家讯8月28日，微软今天推送了Win10预览版10532快速版更新，在该版本中，微软主要是加强细节上调整，并且主要是增强Edge浏览器性能等。在Windows10预览版10532中，微软改进了...
- Win10预览版10532上手视频亮点演示
-
IT之家讯8月28日消息，今天凌晨微软向WindowsInsider快速通道用户推送了Win10预览版10532。在Windows10预览版10532中，微软改进了右键菜单，外观更加现代化。另外还...
- 第二篇 前端框架Vue.js（vue前端框架技术）
-
前端三大核心是网页开发的基础，Vue则是基于它们构建的“生产力工具”。通俗理解就是HTML是化妆的工具如眉笔，CSS是化妆品如口红，JavaScript是化妆后的互动，而Vue就是化妆助手。有了化妆工...
- 基于SpringBoot + vue2实现的旅游推荐管理系统
-
项目描述...
- 基于Vue以及iView组件的后端管理UI模板——iview-admin
-
介绍iView-admin是一套后端管理界面模板，基于Vue2.0，iView（现在为ViewUI）组件是一套完整的基于Vue的高质量组件库，虽然Github上有一套非常火的基于ElementUI...
- 别再说你会SPA开发了，这5个核心你真的搞懂了吗?
-
前言此spa非彼spa,不是你所熟知的spa。你所熟知的spa作者肯定是没有你熟悉的。我们这里指的是在前端开发中的一种模型，叫作单页应用程序，顾名思义，就是整个项目只有一个页面，而页面中的内容是动态的...
- React.js Top20面试题（react.js中文官网）
-
概述作为React开发者，对框架的关键概念和原则有扎实的理解是很重要的。考虑到这一点，我整理了一份包含20个重要问题的清单，每个React开发者都应该知道，无论他们是在面试工作还是只是想提高技能。...
- 美媒:特朗普签署行政令后，FBI又发现约2400份、总计超14000页涉肯尼迪遇刺案文件
-
来源：环球时报新媒体1月23日特朗普下令公布肯尼迪遇刺案相关机密文件图源：美媒综合福克斯新闻网和Axios网站10日报道，在总统特朗普签署行政令，要求公布“肯尼迪遇刺案”相关政府机密文件之后，美国...
- 2021 年 Node.js 开发人员学习路线图
-
Node.js自发布以来，已成为业界重要破局者之一。Uber、Medium、PayPal和沃尔玛等大型企业，纷纷将技术栈转向Node.js。Node.js支持开发功能强大的应用，例如实时追踪...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- Win10预览版10532已知问题汇总（微软win11正式版已知问题一览）
- Gabe Aul正测试Win10 Mobile 10532，Insider用户还需等
- 微软开始推送Win10预览版10532快速版更新
- Win10预览版10532更新内容大全（windows10更新预览版）
- 无法升级Win10预览版10532?也许Hyper-V在搞鬼
- Win10预览版10532界面兴起“酷黑”风潮
- Win10预览版10532上手图集（windows10预览版下载）
- Win10预览版10532上手视频亮点演示
- 第二篇 前端框架Vue.js（vue前端框架技术）
- 基于SpringBoot + vue2实现的旅游推荐管理系统
- 标签列表
-
- idea eval reset (50)
- vue dispatch (70)
- update canceled (42)
- order by asc (53)
- spring gateway (67)
- 简单代码编程 贪吃蛇 (40)
- transforms.resize (33)
- redisson trylock (35)
- 卸载node (35)
- np.reshape (33)
- torch.arange (34)
- npm 源 (35)
- vue3 deep (35)
- win10 ssh (35)
- vue foreach (34)
- idea设置编码为utf8 (35)
- vue 数组添加元素 (34)
- std find (34)
- tablefield注解用途 (35)
- python str转json (34)
- java websocket客户端 (34)
- tensor.view (34)
- java jackson (34)
- vmware17pro最新密钥 (34)
- mysql单表最大数据量 (35)