KMP算法

简介: KMP算法

KMP暴力方法为何暴力?

因为每个位置的尝试对后面位置的尝试都没有任何帮助,每个位置的尝试是独立的!

了解KMP之前,先认识一种信息:前缀与后缀串的最长匹配长度

K之前的字符串中,前缀跟后缀的最长相等长度,而且限定,前缀串不能取到整体,后缀串也不能取到整体。

在这里插入图片描述

package com.harrison.class16;

/**
 * @author Harrison
 * @create 2022-03-29-9:24
 * @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。
 */
public class Code01_KMP {
    public static int getIndexOf(String s1,String s2){
        if(s1==null || s2==null || s2.length()<1 || s1.length()<s2.length()){
            return -1;
        }
        char[] str1=s1.toCharArray();
        char[] str2=s2.toCharArray();
        int x=0;
        int y=0;
        int[] next=getNextArray(str2);
        while(x<s1.length() && y<s2.length()){
            if(str1[x]==str2[y]){
                x++;
                y++;
            }else if(next[y]==-1){// y==0
                x++;
            }else{
                y=next[y];
            }
        }
        // y越界代表 str1的某个开头已经匹配出了str2
        return y==s2.length()?x-y:-1;
    }

    /*
    next[]数组记录:
    1.最长前缀和最长后缀的长度
    2.前缀中下一个字符在哪
     */
    public static int[] getNextArray(char[] str2){
        if(str2.length==1){
            return new int[]{-1};
        }
        int[] next=new int[str2.length];
        next[0]=-1;
        next[1]=0;
        // 目前在哪个位置上求next数组的值
        int i=2;
        // 前缀的下一个字符都跟当前位置的前一个字符比较
        // 当前是哪个位置的值在和i-1位置的字符比较
        int cn=0;
        while(i<next.length){
            if(str2[i-1]==str2[cn]){// 配成功的时候
                next[i++]=++cn;
            }else if(cn>0){
                cn=next[cn];
            }else{
                next[i++]=0;
            }
        }
        return next;
    }

    public static String getRandomString(int possibilities,int size){
        char[] ans=new char[(int)(Math.random()*size)+1];
        for(int i=0; i<ans.length; i++){
            ans[i]=(char)((int)(Math.random()*possibilities)+'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int matchSize = 5;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            String match = getRandomString(possibilities, matchSize);
            if (getIndexOf(str, match) != str.indexOf(match)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }
}
相关文章
|
3月前
|
算法
数据结构中的KMP算法及其改进算法
KMP算法通过引入部分匹配表,有效避免了重复计算,从而将字符串匹配的时间复杂度降低到O(m+n)。通过进一步优化next数组,KMP算法的效率得到了进一步提升。对于大规模字符串匹配问题,KMP算法及其改进算法提供了高效的解决方案,是计算机科学领域的经典算法之一。
49 3
|
23天前
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
|
1月前
|
算法
KMP算法
KMP算法
11 0
|
2月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
2月前
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
|
3月前
|
人工智能 算法 BI
一篇文章讲明白KMP算法(俗称看毛片算法)
一篇文章讲明白KMP算法(俗称看毛片算法)
34 0
|
3月前
|
算法 Java
Java数据结构与算法:字符串匹配算法之KMP算法
Java数据结构与算法:字符串匹配算法之KMP算法
|
4月前
|
算法
|
4月前
|
存储 自然语言处理 算法
【算法】----BF算法&KMP算法
【算法】----BF算法&KMP算法
40 0
|
4月前
|
算法 C语言
KMP算法(C语言实现)
KMP算法(C语言实现)
35 0