Java教程

算法：KMP, str1字符串是否包含str2字符串

本文主要是介绍算法：KMP, str1字符串是否包含str2字符串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【普通解法】从左到右遍历str1的每一个字符，然后看如果 以当前字符作为第一个字符出发 是否匹配 str2字符串。
【KMP算法】
1）生成一个nextArr数组，长度与str2字符串长度一样。i 的 值 含义是 str[0 - i-1】中，必须以str[i-1] 结尾的后缀子串 与 必须以 str[0]开头的前缀子串，最大匹配长度是多少。
快速生成 nextArr数组,先等等
2）
image
假设 str1 从 i 到 j - 1 和 str2 从 0 到 j-1一样。从j不一样了。
然后str2的索引退回到 t2 索引 继续 和 str1的 j匹配。 圆圈就代表 最长前缀子串。

str1 索引不回退，是因为 中间其他位置不可能再完全匹配 str2了。
使用反证法：
image
假设str1 能从 k开始能够完全 匹配 str2. 看虚线部分。
说明 虚线1 和 虚线2 一样。
又因为str1 和 str2 从 0 到 j-1 一样。说明 虚线 1 和 虚线 3 一样。
那么 虚线2 和虚线3 一样，那么最长前缀子串 就不是咱开始的了。
如果咱的最长子串 算的是对的，那么 str1索引从j开始就没问题。

这篇关于算法：KMP, str1字符串是否包含str2字符串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航