• acwing KMP算法java版实现

    题目所属分类

    属于典型的KMP算法

    原题链接

    在这里插入图片描述

    代码案例：输入样例：
    3
    aba
    5
    ababa
    输出样例：
    0 2

    题解

    KMP的朴素做法
    在这里插入图片描述解释next[i]=j的含义 可以把j当作常数那么看
    理解j=ne[j]，首先我们需要理解ne[i]=j
    ne[i]=j表示：ne[i]表示当有i个字符时最大前缀后缀的共同元素个数为j

    在这里插入图片描述理解j=next[j]
    在这里插入图片描述

    如果说单说模板串p 而言 那么j那点的坐标就是等于next[j]
    那就可以理解为匹配最长公共前后缀的下标为next[j]
    因为需要三段相等 所以j那个点就等于next[j]在这里插入图片描述
    1和3相等意思就是next的含义 而我们希望移动到下一个匹配的地方
    也就是直接让1和2相等
    在这里插入图片描述
    s[ a , b ] = p[ 1, j ] && s[ i ] != p[ j + 1 ] 此时要移动p串（不是移动1格，而是直接移动到下次能匹配的位置）

    其中1串为[ 1, next[ j ] ]，3串为[ j - next[ j ] + 1 , j ]。由匹配可知 1串等于3串，3串等于2串。所以直接移动p串使1到3的位置即可。

    这个操作可由j = next[ j ]直接完成。 如此往复下去，当 j == m时匹配成功。
    这时候可以看成

    for(int i = 1, j = 0; i <= n; i++)
{//j不能退回起点
    while(j > 0 && s[i] != p[j+1]) j = ne[j];
    //如果j有对应p串的元素， 且s[i] != p[j+1], 则失配， 移动p串
    //用while是由于移动后可能仍然失配，所以要继续移动直到匹配或整个p串移到后面（j = 0)

    if(s[i] == p[j+1]) j++;
    //当前元素匹配，j移向p串下一位
    if(j == n)
    {
        //匹配成功，进行相关操作
        j = next[j];  //继续匹配下一个子串
    }
}

 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    求next数组的过程（详细版见）

    在这里插入图片描述

    在这里插入图片描述在这里插入图片描述

    for(int i = 2, j = 0; i <= m; i++)
{
    while(j > 0 && p[i] != p[j+1]) j = next[j];

    if(p[i] == p[j+1]) j++;

    next[i] = j;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    完整注释代码如下

    输出没用BufferedReader总是显示超时

    import java.io.*;
public class Main{
    static int N = 100010,M = 1000010;
    static char[] p = new char[N];
    static char[] s = new char[M];
    static int[] ne = new int[N];
    public static void main(String[] args)throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n  = Integer.parseInt(in.readLine());//输入p字符的长度
        String arr = in.readLine();
        //下标要从1开始
        for(int i = 1 ; i <= n ; i++){
            p[i] = arr.charAt(i-1);//输入p字符串  
        }
        int m  = Integer.parseInt(in.readLine());
        String cur = in.readLine();
         for(int i = 1 ; i <= m ; i++){
            s[i] = cur.charAt(i-1);//输入s字符串
        }
        
          //这里从2开始是因为 ne[1]=0 
        for(int i = 2 , j = 0; i  <= n ; i ++ ){
            //这里判断从j是不是大于0，如果小于0，表示还没有前缀和后缀相等
            //如果出现下一个数与j+1这个数不相等就让j等于上一个数的next[];
            while(j > 0 && p[i] != p[j+1]) j = ne[j];
            //如果j+1等于i这个数时候，就让j++，说明有有一个相等，前缀和后缀相等长度为1.
            if(p[i] == p[j+1]) j ++ ;
            //然后将相等的缀长度存入next[]数组中；
            ne[i] = j;
        }
        //KMP匹配代码
         for(int i = 1 ,j = 0; i <= m ; i++){
              //判断j是不是大于0，小于0表示还没有前缀和后缀相等
            //判断长的数组一个一个遍历比较，看看短的数组，如果不相等就让j = 上一个数的缀长度
             while(j > 0 && s[i] != p[j+1]) j = ne[j];
              //如果相等就让j++；继续进行下一个数的比较
             if(s[i] == p[j+1]) j++;
             //如果相等的数等于短的数组的长度，就说明该输出了
            if(j == n){
               System.out.print((i - n) + " ");//正常情况下输出下标为i-n+1 由于答案要求从0开始 所以在-1
                //输出之后，要继续往下面遍历对比，所以让j=上一个数的缀长度，
                //因为有前缀和后缀相等的部分可以重复使用 也就是可以循环去做 往后在移动ne[j]个长度
                j = ne[j];
            }
         }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    换程了那种就不超时了

    import java.io.*;
public class Main{
    static int N = 100010,M = 1000010;
     
    static int[] ne = new int[N];
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wt = new BufferedWriter(new OutputStreamWriter(System.out));
         int n  = Integer.parseInt(bf.readLine());//输入p字符的长度
        String P =  bf.readLine();//输入p字符串
        char[] p = new char[N];
    
        for(int i = 1 ; i <= n ; i ++ ) p[i] = P.charAt(i-1);
        int m = Integer.parseInt(bf.readLine());//输入s字符串的长度
        String S = bf.readLine();//输入s字符串
        char[] s = new char[M];
        for(int i = 1 ; i <= m ; i ++ ) s[i]  = S.charAt(i-1);
 
        
        
        // int n  = Integer.parseInt(in.readLine());//输入p字符的长度
        // String arr = in.readLine();//输入p字符串 
        // //下标要从1开始
        // for(int i = 1 ; i <= n ; i++){
        //     p[i] = arr.charAt(i-1); 
        // }
        // int m  = Integer.parseInt(in.readLine());
        // String cur = in.readLine();
        //  for(int i = 1 ; i <= m ; i++){
        //     s[i] = cur.charAt(i-1);//输入s字符串
        // }
        
          //这里从2开始是因为 ne[1]=0 
        for(int i = 2 , j = 0; i  <= n ; i ++ ){
            //这里判断从j是不是大于0，如果小于0，表示还没有前缀和后缀相等
            //如果出现下一个数与j+1这个数不相等就让j等于上一个数的next[];
            while(j > 0 && p[i] != p[j+1]) j = ne[j];
            //如果j+1等于i这个数时候，就让j++，说明有有一个相等，前缀和后缀相等长度为1.
            if(p[i] == p[j+1]) j ++ ;
            //然后将相等的缀长度存入next[]数组中；
            ne[i] = j;
        }
        //KMP匹配代码
         for(int i = 1 ,j = 0; i <= m ; i++){
              //判断j是不是大于0，小于0表示还没有前缀和后缀相等
            //判断长的数组一个一个遍历比较，看看短的数组，如果不相等就让j = 上一个数的缀长度
             while(j > 0 && s[i] != p[j+1]) j = ne[j];
              //如果相等就让j++；继续进行下一个数的比较
             if(s[i] == p[j+1]) j++;
             //如果相等的数等于短的数组的长度，就说明该输出了
            if(j == n){
                wt.write((i - n) + " ");//正常情况下输出下标为i-n+1 由于答案要求从0开始 所以在-1
                //输出之后，要继续往下面遍历对比，所以让j=上一个数的缀长度，
                //因为有前缀和后缀相等的部分可以重复使用 也就是可以循环去做 往后在移动ne[j]个长度
                j = ne[j];
            }
         }
           wt.flush();
        wt.close();
        bf.close();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    不过要注意flush()操作

    import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
public class Main{
    static int N = 100010;
    static int ne[] = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Integer n = Integer.parseInt(br.readLine());
        String s1 = " " + br.readLine();
        Integer m = Integer.parseInt(br.readLine());
        String s2 = " " + br.readLine();
        char[] a1 = s1.toCharArray();
        char[] a2 = s2.toCharArray();
        /**
         * ne[]：存储一个字符串以每个位置为结尾的‘可匹配最长前后缀’的长度。
         * 构建ne[]数组：
         *              1,初始化ne[1] = 0,i从2开始。
         *              2,若匹配，s[i]=s[j+1]说明1~j+1是i的可匹配最长后缀,ne[i] = ++j;
         *              3,若不匹配，则从j的最长前缀位置+1的位置继续与i比较
         *              (因为i-1和j拥有相同的最长前后缀，我们拿j的前缀去对齐i-1的后缀),
         *              即令j = ne[j],继续比较j+1与i，若匹配转->>2
         *              4,若一直得不到匹配j最终会降到0，也就是i的‘可匹配最长前后缀’的长度
         *              要从零开始重新计算
         */
        for(int i = 2,j = 0;i <= n ;i++) {
            while(j!=0&&a1[i]!=a1[j+1]) j = ne[j]; 
            if(a1[i]==a1[j+1]) j++;
            ne[i] = j;
        }
        /**
         * 匹配两个字符串：
         *      1，从i=1的位置开始逐个匹配，利用ne[]数组减少比较次数
         *      2，若i与j+1的位置不匹配（已知1~j匹配i-j~i-1)，
         *      j跳回ne[j]继续比较(因为1~j匹配i-j~i-1,所以1~ne[j]也能匹配到i-ne[j]~i-1)
         *      3，若匹配则j++,直到j==n能确定匹配成功
         *      4，成功后依然j = ne[j],就是把这次成功当成失败，继续匹配下一个位置
         */
        for(int i = 1,j = 0; i <= m;i++) {
            while(j!=0&&a2[i]!=a1[j+1]) j = ne[j];
            if(a2[i]==a1[j+1]) j++;
            if(j==n) {
                j = ne[j];
                bw.write(i-n+" ");
            }
        }
        /**
         * 时间复杂度：
         *      因为：j最多加m次，再加之前j每次都会减少且最少减一，j>0
         *      所以：while循环最多执行m次,若大于m次，j<0矛盾
         *      最终答案：O(2m)
         */
        bw.flush();
    }
}

 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
  • 相关阅读:
    NX二次开发-几款辅助学习NX开发的搜索软件
    CVPR2023优秀论文 | AIGC伪造图像鉴别算法泛化性缺失问题分析
    【JUC】九、线程池ThreadPool
    Maven
    DES & 3DES 简介 以及 C# 和 js 实现【加密知多少系列】
    java简介
    Java的方法
    【upload靶场12-16】截断、图片马
    责任链模式
    基于TNEWS‘ 今日头条中文新闻（短文本）分类
  • 原文地址：https://blog.csdn.net/qq_41810415/article/details/126260645