当前位置：网站首页 > 技术分类 > 正文

JAVA字符串算法——KMP算法（java的kmp算法）

ztj100 2025-07-15 02:16 11 浏览 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]

js substring

上一篇：数据结构之串的详解（数据结构中串的概念）
下一篇：Java，一天一个知识点之:循环结构:for与while循环的使用场景

JAVA字符串算法——KMP算法（java的kmp算法）

相关推荐

取消回复欢迎你发表评论:

MySQL中这14个小玩意，让人眼前一亮!

旗舰机新标杆 OPPO Find X2系列正式发布售价5499元起

面试官:使用int类型做加减操作，是线程安全吗

C++编程知识:ToString()字符串转换你用正确了吗?

【Spring Boot】WebSocket 的 6 种集成方式

PyTorch 深度学习实战(26):多目标强化学习Multi-Objective RL

pytorch中的 scatter_()函数使用和详解

与 Java 17 相比，Java 21 究竟有多快?

基于TensorRT_LLM的大模型推理加速与OpenAI兼容服务优化

这一次，彻底搞懂Java并发包中的Atomic原子类

JAVA字符串算法——KMP算法（java的kmp算法）

相关推荐

取消回复欢迎 你 发表评论:

MySQL中这14个小玩意，让人眼前一亮!

旗舰机新标杆 OPPO Find X2系列正式发布 售价5499元起

面试官:使用int类型做加减操作，是线程安全吗

C++编程知识:ToString()字符串转换你用正确了吗?

【Spring Boot】WebSocket 的 6 种集成方式

PyTorch 深度学习实战(26):多目标强化学习Multi-Objective RL

pytorch中的 scatter_()函数使用和详解

与 Java 17 相比，Java 21 究竟有多快?

基于TensorRT_LLM的大模型推理加速与OpenAI兼容服务优化

这一次，彻底搞懂Java并发包中的Atomic原子类

取消回复欢迎你发表评论:

旗舰机新标杆 OPPO Find X2系列正式发布售价5499元起