欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Hdu1711-Number Sequence以及KMP算法总结

程序员文章站 2022-06-11 13:33:24
...

Hdu1711-Number Sequence以及KMP算法总结

  • KMP求解流程
  • KMPnext数组求解
  • Hdu1711-Number Sequence模板题

题目链接

KMP求解流程

这里先说明next数组的含义:

  • next[i]的含义是在str[i]之前的字符串str[0…i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前缀子串(不能包含str[i-1])的最大匹配长度,这里我们先认为已经求得了匹配串的这个next数组(后面讲next数组求解)。

然后再看KMP求解流程:

  • 当主串的指针i1和匹配串的指针i2所在位置str1[i1] == str2[i2]的时候,i1++,i2++;
  • 否则,让i2直接跳到i2位置的next数组的值的位置,也就是i2 = next[i2],这个过程相当于str2向右推动,看下图的两个失配的做法,当然,如果next[i2] = -1了,说明i2到了0位置,开头都配不上,那i1++吧;

Hdu1711-Number Sequence以及KMP算法总结


KMPnext数组求解

next数组使用的数学归纳法,不断的分开往前面匹配的过程:

看下面求解k位置的next的做法 –>得出的结论是next[k] = 0;

Hdu1711-Number Sequence以及KMP算法总结

再看一个普通的情况: (可以匹配成功的情况)
Hdu1711-Number Sequence以及KMP算法总结

根据上面的分析写出代码

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Kmp {

    public static int kmp(String s,String p){
        if(s == null || p == null || p.length() < 1 || s.length() < p.length() )return -1;
        char[] str1 = s.toCharArray();
        char[] str2 = p.toCharArray();

        int i1 = 0,i2 = 0; //甲乙
        int[] next = getNext(str2);
        while(i1 < str1.length && i2 < str2.length){
            if(str1[i1] == str2[i2]){ //能配上,继续
                i1++; i2++;
            }else {
                if(next[i2] == -1) { //我str2到了第一个你都配不上,那你str1就下一个吧
                    i1++;
                }else {//逻辑概念是str2往右边推
                    i2 = next[i2]; //来到next数组指示(最长公共前缀后缀)
                }
            }
        }
        return i2 == str2.length ? i1 - i2 : -1;
    }

    /**
     * next数组的求法
     * @param str2
     * @return
     */
    private static int[] getNext(char[] str2) {
        if(str2.length == 1)return new int[]{-1};
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        for(int i = 2; i < str2.length;){
            if(str2[i-1] == str2[cn]){
                next[i++] = ++cn; //就是cn+1
            }else {
                if(cn > 0) cn = next[cn];
                else next[i++] = 0;
            }
        }
        return next;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        while(n-- > 0){
            String s = cin.next();//主串
            String p = cin.next();//匹配串
            System.out.println(kmp(s,p));
        }
    }
}

Hdu1711-Number Sequence模板题

这个就是一个KMP最简单的模板题,将字符串改成数组就ok了

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    private static int kmp(int[] s,int[] p){
        if(s == null || p == null || s.length < p.length || p.length == 0)return -1;
        int[] next = getNext(p);
        int i1 = 0,i2 = 0;
        while(i1 < s.length && i2 < p.length){
            if(s[i1] == p[i2]) {
                i1++; i2++;
            }else {
                if(next[i2] == -1){
                    i1++;
                }else {
                    i2 = next[i2];
                }
            }
        }
        return i2 == p.length ? i1 - i2 : -1;

    }

    private static int[] getNext(int[] arr){
        if(arr.length == 1)return new int[]{-1};
        int[] next = new int[arr.length];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        for(int i = 2; i < arr.length; ){
            if( arr[i-1] == arr[cn]){
                next[i++] = ++cn;
            }else {
                if(cn > 0){
                    cn = next[cn];
                }else {
                    next[i++] = 0;
                }
            }
        }
        return next;
    }


    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int k = cin.nextInt();
        while (k-- > 0) {
            int n = cin.nextInt();
            int m = cin.nextInt();
            int[] s = new int[n], p = new int[m];//切记ACM题中这个长度是很重要的,不能随便new int[n+1]因为后面用length代替了n
            for(int i = 0; i < n; i++)s[i] = cin.nextInt();
            for(int i = 0; i < m; i++)p[i] = cin.nextInt();
            int res = kmp(s,p);
            System.out.println(res == -1 ? -1 : res+1);
        }
    }
}