JAVA字符串算法——KMP算法
wxin55 2024-11-17 16:47 9 浏览 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]
相关推荐
- ES6中 Promise的使用场景?（es6promise用法例子）
-
一、介绍Promise，译为承诺，是异步编程的一种解决方案，比传统的解决方案（回调函数）更加合理和更加强大在以往我们如果处理多层异步操作，我们往往会像下面那样编写我们的代码doSomething(f...
- JavaScript 对 Promise 并发的处理方法
-
Promise对象代表一个未来的值，它有三种状态：pending待定，这是Promise的初始状态，它可能成功，也可能失败，前途未卜fulfilled已完成，这是一种成功的状态，此时可以获取...
- Promise的九大方法（promise的实例方法）
-
1、promise.resolv静态方法Promise.resolve(value)可以认为是newPromise方法的语法糖,比如Promise.resolve(42)可以认为是以下代码的语...
- 360前端一面~面试题解析（360前端开发面试题）
-
1.组件库按需加载怎么做的，具体打包配了什么-按需加载实现：借助打包工具（如Webpack的require.context或ES模块动态导入），在使用组件时才引入对应的代码。例如在V...
- 前端面试-Promise 的 finally 怎么实现的?如何在工作中使用?
-
Promise的finally方法是一个非常有用的工具，它无论Promise是成功（fulfilled）还是失败（rejected）都会执行，且不改变Promise的最终结果。它的实现原...
- 最简单手写Promise，30行代码理解Promise核心原理和发布订阅模式
-
看了全网手写Promise的，大部分对于新手还是比较难理解的，其中几个比较难的点：状态还未改变时通过发布订阅模式去收集事件实例化的时候通过调用构造函数里传出来的方法去修改类里面的状态，这个叫Re...
- 前端分享-Promise可以中途取消啦（promise可以取消吗）
-
传统Promise就像一台需要手动组装的设备，每次使用都要重新接线。而Promise.withResolvers的出现，相当于给开发者发了一个智能遥控器，可以随时随地控制异步操作。它解决了三大...
- 手写 Promise（手写输入法 中文）
-
前言都2020年了，Promise大家肯定都在用了，但是估计很多人对其原理还是一知半解，今天就让我们一起实现一个符合PromiseA+规范的Promise。附PromiseA+规范地址...
- 什么是 Promise.allSettled()!新手老手都要会?
-
Promise.allSettled()方法返回一个在所有给定的promise都已经fulfilled或rejected后的promise，并带有一个对象数组，每个对象表示对应的pr...
- 前端面试-关于Promise解析与高频面试题示范
-
Promise是啥，直接上图：Promise就是处理异步函数的API，它可以包裹一个异步函数，在异步函数完成时抛出完成状态，让代码结束远古时无限回掉的窘境。配合async/await语法糖，可...
- 宇宙厂:为什么前端离不开 Promise.withResolvers() ?
-
大家好，很高兴又见面了，我是"高级前端进阶"，由我带着大家一起关注前端前沿、深入前端底层技术，大家一起进步，也欢迎大家关注、点赞、收藏、转发。1.为什么需要Promise.with...
- Promise 新增了一个超实用的 API!
-
在JavaScript的世界里，Promise一直是处理异步操作的神器。而现在，随着ES2025的发布，Promise又迎来了一个超实用的新成员——Promise.try()！这个新方法简...
- 一次搞懂 Promise 异步处理（promise 异步顺序执行）
-
PromisePromise就像这个词的表面意识一样，表示一种承诺、许诺，会在后面给出一个结果，成功或者失败。现在已经成为了主流的异步编程的操作方式，写进了标准里面。状态Promise有且仅有...
- Promise 核心机制详解（promise机制的实现原理）
-
一、Promise的核心状态机Promise本质上是一个状态机，其行为由内部状态严格管控。每个Promise实例在创建时处于Pending（等待）状态，此时异步操作尚未完成。当异步操作成功...
- javascript——Promise（js实现promise）
-
1.PromiseES6开始支持，Promise对象用于一个异步操作的最终完成（包括成功和失败）及结果值的表示。简单说就是处理异步请求的。之所以叫Promise，就是我承诺，如果成功则怎么处理，失败怎...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- ES6中 Promise的使用场景?（es6promise用法例子）
- JavaScript 对 Promise 并发的处理方法
- Promise的九大方法（promise的实例方法）
- 360前端一面~面试题解析（360前端开发面试题）
- 前端面试-Promise 的 finally 怎么实现的?如何在工作中使用?
- 最简单手写Promise，30行代码理解Promise核心原理和发布订阅模式
- 前端分享-Promise可以中途取消啦（promise可以取消吗）
- 手写 Promise（手写输入法 中文）
- 什么是 Promise.allSettled()!新手老手都要会?
- 前端面试-关于Promise解析与高频面试题示范
- 标签列表
-
- hive行转列函数 (63)
- sourcemap文件是什么 (54)
- display none 隐藏后怎么显示 (56)
- 共享锁和排他锁的区别 (51)
- httpservletrequest 获取参数 (64)
- jstl包 (64)
- qsharedmemory (50)
- watch computed (53)
- java中switch (68)
- date.now (55)
- git-bash (56)
- 盒子垂直居中 (68)
- npm是什么命令 (62)
- python中+=代表什么 (70)
- fsimage (51)
- nginx break (61)
- mysql分区表的优缺点 (53)
- centos7切换到图形界面 (55)
- 前端深拷贝 (62)
- kmp模式匹配算法 (57)
- jsjson字符串转json对象 (53)
- jdbc connection (61)
- javascript字符串转换为数字 (54)
- mybatis 使用 (73)
- 安装mysql数据库 (55)