温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

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

发布时间:2021-12-20 14:48:17 来源:亿速云 阅读:138 作者:iii 栏目:大数据

这篇文章主要讲解了“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"));    }}

对于暴力算法,如果出现不匹配字符,同时回退 txtpat 的指针,嵌套 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算法怎么写这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI