By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、实现strStr(匹配字符串)

实现 strStr() 函数。

给定一个 txt字符串和一个 pattern 字符串，在 txt字符串中找出 pattern 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: txt = "hello", pattern  = "ll"
输出: 2

示例 2:

输入: txt = "aaaaa", pattern  = "bba"
输出: -1

说明: 当 pattern是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

解答：空字符串肯定是匹配的，返回0，

1.1、解题思路 :KMP 算法

1.1.1、KMP 算法是什么

KMP 算法是一种字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特—莫里斯—普拉特算法（简称KMP算法）。

1.1.2、暴力法

在暴力匹配中，我们在 txt 中从 i 开始与 pattern 串匹配，一旦匹配失败，则从 i + 1 子串重新匹配。此时我们抛弃了前面的匹配信息，因为我们知道前面匹配中遇到了四，而 pattern 中并无 四 ，应该从 四 后面的 一 开始重新匹配。

1.1.3、KMP图解

KMP 算法目的就是：在出错时，利用原有的匹配信息，尽量减少重新匹配的次数。

在两种方法的对比中，可以看到 KMP 算法的主串下标永不后退，而暴力算法一旦出错，则回退至匹配起始的下一个下标重头开始。

1、对于已经匹配到这种状态的两个字符串

1583839470449

2、 移动位数 = 已匹配的字符数 - 对应的部分匹配值，因为 6 - 2 等于4，所以将搜索词向后移动4位。

1583839457079

3、因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

1583839624497

4、因为空格与A不匹配，继续后移一位。

1583839662954

5、逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

1583839706711

6、逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

1.1.4、部分匹配表如何产生

上面我们会看到有部分匹配，要有使用KMP算法，就必须知道部分匹配是从哪里来的

首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

1.1.4.1、前缀和后缀

如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示： 为了记录这些信息我们将会一个next数组来记录每一个字符的部分匹配值。

前缀是除了最后一个字符的子字符串，后缀是指除了第一个字符的子字符串

1583839931854

1.1.4.2、求next数组

i 0 1 2 3 4 5 6 7
字符串 A B C D A B D ’‘\0’
next[i] 0 0 0 0 0 1 2 0

假设我们现在已经求得 next[1]、next[2]、……、next[i]，现在要求next[i+1]。通过上面的表格可以看出，（这个时候极端一点，那加入字符串为AA呢，因为第二个字符串A签名只有一个A，后缀长度为0，所以是0）

如果字符串位置 `i `和位置 `next[i] `处的两个字符相同，则 `next[i+1]` = `next[i] + 1`；

如果两个位置的字符不相同，可以继续向前搜索，如果两个位置的字符不相同，可以继续向前搜索，获得其最大公共长度 `next[next[i]]`，然后再和位置 i 的字符比较，直到能最终确，

那么，为什么根据最长相同真前后缀的长度就可以实现在不匹配情况下的跳转呢？

举个代表性的例子：假如`i = 6`时不匹配，此时我们是知道其位置前的字符串为`ABCDAB`，仔细观察这个字符串，首尾都有一个`AB`，既然在`i = 6`处的D不匹配，我们为何不直接把`i = 2`处的`C`拿过来继续比较呢，因为都有一个`AB`啊，而这个`AB`就是`ABCDAB`的**最长相同真前后缀**，其长度`2`正好是跳转的下标位置

。

/**
     * 获取next数组
     */
    public static int[] getNext(String find) {

        int[] next = new int[find.length()];
        if (find.length() ==1){
            next[0] = 0;
            return next;
        }
        //第一个和第二个是0，因为同时不存在前缀和后缀
        next[0] = 0;
        next[1] = 0;

        // 因为 next[0]  next[1] 已经确定了，要开始找 next[2]，所以初始化 i = 1
        // k 为 next[i] 当前的值，初始化的时候，next[1] = 0 ,所以k为0
        int i = 1, k = 0;
        // 所以i next[i+1] 是通过 next[i] 求的，i 不会超过 sub.length() - 1
        while (i < find.length() - 1) {
            //如果字符串位置 `i `和位置 `next[i] `处的两个字符相同，则 `next[i+1]` = `next[i] + 1`
            if (find.charAt(i) == find.charAt(k)) {
                next[i + 1] = k + 1;
                //因为上面 k 为next[i]，while下一步执行的就是i + 1
                //上面 next[i + 1] 已经给出值了，所以继续执行while的话， i 和 k 都要加 1（i指针移动加1，k为值加1）
                i++;
                k++;
            } else if (k == 0) {
                //k = 0 并且没有匹配，当然为0喽，k也不需要+1了
                next[i + 1] = 0;
                i++;
            } else {
                // 往前好回溯，这个时候k是大于0的，但是上面第一个比较的时候，没有成功。
                // 为了再类似于暴力法那样重新开始匹配，按照我们找出的规律往前回溯，代表性例子就知道了
                k = next[k];
            }
        }
        return next;
    }

1.2、算法


public int strStr(String txt, String pattern) {
    if (pattern.length() == 0) {
        return 0;
    }
    if (txt.length() == 0){
        return -1;
    }

    //i 表示 text 中的位置，j 表示 find 中的位置
    int[] next = getNext(pattern);
    //遍历 txt 中的字符
    for (int i = 0, j = 0; i < txt.length(); i++) {
        //while放在开头，因为是刚刚开始匹配，如果不成立，next数组马上回溯
        // j!= 0 但是不相等，表示刚刚经过匹配，这里是 KMP 算法的关键点，移动位置为回溯 next[j]
        while (j != 0 && txt.charAt(i) != pattern.charAt(j)) {
            j = next[j];
        }
        //如果 i 位置和 j 位置的字符相同，待匹配字符串移动一位
        if (txt.charAt(i) == pattern.charAt(j)) {
            j++;
        }

        //在上面的if中 j++ 会比指针大1，当j等于待匹配长度的时候，表示到结尾了
        if (j == pattern.length()) {
            // i当前匹配到的地方，最后求的是txt字符串刚开始匹配的位置，所以 i - j + 1
            return i - j + 1;
        }
    }
    return -1;
}


/**
     * 获取next数组
     */
public static int[] getNext(String find) {

    int[] next = new int[find.length()];
    if (find.length() ==1){
        next[0] = 0;
        return next;
    }
    //第一个和第二个是0，因为同时不存在前缀和后缀
    next[0] = 0;
    next[1] = 0;

    // 因为 next[0]  next[1] 已经确定了，要开始找 next[2]，所以初始化 i = 1
    // k 为 next[i] 当前的值，初始化的时候，next[1] = 0 ,所以k为0
    int i = 1, k = 0;
    // 所以i next[i+1] 是通过 next[i] 求的，i 不会超过 sub.length() - 1
    while (i < find.length() - 1) {
        //如果字符串位置 `i `和位置 `next[i] `处的两个字符相同，则 `next[i+1]` = `next[i] + 1`
        if (find.charAt(i) == find.charAt(k)) {
            next[i + 1] = k + 1;
            //因为上面 k 为next[i]，while下一步执行的就是i + 1
            //上面 next[i + 1] 已经给出值了，所以继续执行while的话， i 和 k 都要加 1（i指针移动加1，k为值加1）
            i++;
            k++;
        } else if (k == 0) {
            //k = 0 并且没有匹配，当然为0喽，k也不需要+1了
            next[i + 1] = 0;
            i++;
        } else {
            // 往前好回溯，这个时候k是大于0的，但是上面第一个比较的时候，没有成功。
            // 为了再类似于暴力法那样重新开始匹配，按照我们找出的规律往前回溯，代表性例子就知道了
            k = next[k];
        }
    }
    return next;
}

1.3、测试


    @Test
    public void test(){
        System.out.println(Arrays.toString(getNext("issip")));
        System.out.println(strStr("mississippi", "issip"));
    }

ContactAuthor