个人博客
www.tothefor.com
蓝桥杯复习知识点汇总

目录

KMP

应用1：是否存在子串

import java.util.Scanner;

/**
 * @Author DragonOne
 * @Date 2021/12/11 07:00
 * @墨水记忆 www.tothefor.com
 */

//是否匹配或输出第一次匹配的位置
public class kmp1 {
    final static int maxn = (int) 1e7 + 6;
    public static char[] a = new char[maxn];
    public static char[] b = new char[maxn];
    public static int[] ne = new int[maxn];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        a = s.toCharArray();
        String ss = sc.next();
        b = ss.toCharArray();
        System.out.println(kmp(a,b));
    }

    public static void getnext(char[] x) {
        ne[0] = -1;
        int len = x.length;
        int i = 0, j = -1;
        while (i < len-1) {
            if (j == -1 || x[i] == x[j]) {
                ne[++i] = ++j;
            } else j = ne[j];
        }
    }

    public static int kmp(char[] x, char[] y) {
        getnext(y);
        int xlen = x.length;
        int ylen = y.length;
        int i = 0, j = 0;
        int ans = 0;
        while (i < xlen && j < ylen) {
            if (j == -1 || x[i] == y[j]) {
                i++;
                j++;
            } else
                j = ne[j];
        }
        if (j == ylen)
            return 1; //        若 return i-ylen; 为返回第一次匹配时在原串中的位置
        else
            return 0;
    }
}

应用2：所有的子串及其位置

import java.util.Scanner;

/**
 * @Author DragonOne
 * @Date 2021/12/11 07:06
 * @墨水记忆 www.tothefor.com
 */

//输出所有匹配下标及其总次数
public class kmp2 {
    final static int maxn = (int) 1e7 + 6;
    public static char[] a = new char[maxn];
    public static char[] b = new char[maxn];
    public static int[] ne = new int[maxn];
    public static int ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        a = s.toCharArray();
        String ss = sc.next();
        b = ss.toCharArray();
        kmp(a, b);
        System.out.println("总共匹配的次数为" + ans);
    }

    public static void getnext(char[] x) {
        ne[0] = -1;
        int len = x.length;
        int i = 0, j = -1;
        while (i < len-1) {
            if (j == -1 || x[i] == x[j]) {
                ne[++i] = ++j;
            } else j = ne[j];
        }
    }

    public static void kmp(char[] x, char[] y) { //x为原串，y为模式串
        getnext(y);
        int xlen = x.length;
        int ylen = y.length;
        int i = 0, j = 0;
        while (i < xlen && j < ylen) { //j<ylen在这里实际并没有起作用
            if (j == -1 || x[i] == y[j]) {
                i++;
                j++;
                if (j == ylen) {
                    ans++;
                    System.out.println(i - j + " "); //子串的开始下标
                    j = ne[j];
                }
            } else j = ne[j];
        }
    }

}

next数组优化

如表格，若在i = 5时匹配失败，此时应该把i = 1处的字符拿过来继续比较，但是这两个位置的字符是一样的，都是B，既然一样，拿过来比较就是无用功了。就需要再找前一个不同的为止。

public static void getnext(char[] x) {
  ne[0] = -1;
  int len = x.length;
  int i = 0, j = -1;
  while (i < len-1) {
    if (j == -1 || x[i] == x[j]) {
        ++i;
        ++j;
        if (P[i] != P[j])
          ne[i] = j;
        else
          ne[i] = ne[j];  // 既然相同就继续往前找真前缀
    } else j = ne[j];
  }
}

📢提示：能不用优化的尽量不用优化，因为优化已经改变了next数组的本质，即最大前缀后缀匹配，也就是说，我们只是为了查询得更快而进行数据存储方式的优化，对于一些利用next本质的题目，这样的优化可能会出现意想不到的错误，甚至反而会超时。如 POJ2752 ，因此优化KMP不能完全替代朴素KMP。

拓展

1. BM算法。

2. Sunday算法。