Java中字符串匹配KMP算法怎么写

这篇文章主要讲解了“Java中字符串匹配KMP算法怎么写”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Java中字符串匹配KMP算法怎么写”吧！

暴力的字符串匹配算法很容易写，看一下它的运行逻辑：

public class bf {    public static int search(String txt,String pat){        int sLen = txt.length();// 主字符串        int pLen = pat.length();// 模式串长度        // 需要匹配的次数        for (int i=0;i<=sLen-pLen;i++){            int j ;            // 遍历模式串            for (j=0;j<pLen;j++){                if (pat.charAt(j)!=txt.charAt(i+j)){                    break;                }            }            // 如果j移动到模板末尾了 说明匹配成功了            if (j==pLen) return i ;        }        return -1;    }    public static void main(String[] args) {        System.out.println(search("aaacaaab","ababac"));    }}

对于暴力算法，如果出现不匹配字符，同时回退 txt 和 pat 的指针，嵌套 for 循环，时间复杂度 $O(MN)$，空间复杂度$O(1)$。最主要的问题是，如果字符串中重复的字符比较多，该算法就显得很蠢。

比如 txt = "aaacaaab" pat = "aaab"：

求

KMP分为两部分，next 数组 和 正式匹配

next 数组 部分：开一个数组next，找每个字符前的 最大相等前后缀长度，我简单地通过举例解释一下这个词：

比如 aba --> 一个前缀是 a，一个后缀是 a，最大相等前后缀长度 为 1

比如 baba --> 一个前缀是 ba，一个后缀是 ba，最大相等前后缀长度 为 2

比如 ababa --> 一个前缀是 aba，一个后缀是 aba，最大相等前后缀长度 为 3，为什么不是前缀 ababa，后缀 ababa 呢，是因为前缀不包含最后一个字符，后缀不包含第一个字符。为什么不是前缀 a 后缀 a 呢，因为尽管它们是一对相等前后缀，但它们不是 最大 相等前后缀长度

设置i j指针，i j最初位于开头和索引为 1 的位置，分别代表前缀，后缀指针，前缀后缀串有个特点：前缀串总是从0开始，而后缀串总是相对于前缀串(不能确定开始的位置)，因此每当 i j 失配时，i 就回溯到上一个位置，那 i 怎么回到上一个位置，这个地方是最难理解的：next[i] 就是 i 应该回到的位置（ps:如果你是为了考试但还不能理解，建议背下来，可以不用花时间去理解了，始终记住一回溯就是 i = next[i]，如果放一堆证明公式在这里，相信肯定令人昏昏欲睡！）然后进行下一轮匹配，直到 j 走完了，next数组才算完成

正式匹配 部分：现在来讨论主串与模式串的关系了，主串就是被匹配的串，模式串是要拿去匹配的其他字符串的字符串(有点拗口)，通常模式串长度小于主串。用 i j 作为主串 模式串的指针，这时模式串是相对的，主串是绝对的，因为主串匹配不上就得往后走，而模式串匹配不上就得再重新匹配前面一部分，因此每当 i j 失配时，j 就回溯到上一个位置(这里的回溯同理)，进行下一轮匹配，直到 j 走完了，说明匹配成功，返回 i - j，因为i - j 对应的就是匹配到的起始位置。若匹配不上的话，i 就走到结尾了，返回 -1

感谢各位的阅读，以上就是“Java中字符串匹配KMP算法怎么写”的内容了，经过本文的学习后，相信大家对Java中字符串匹配KMP算法怎么写这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！