原题

实现 strStr() 函数。

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

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

说明:

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

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

解法

JDK API

在leetcode上，当然可以投机取巧地使用String.indexof()方法，不用重复造轮子：

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

但这是一个经典的字符串精准模式匹配问题，历史上出现过很多解决这个问题的算法，掌握它们的思想还是有必要的：

BF算法（朴素算法）

思想

这是最直观、最简单的算法。从主串的第start个字符起和模式的第1个字符比较，如果相等继续逐个比较后续字符。比较过程中一旦发现不相等的情况，则回溯至主串中的第start+1个字符位置处，重新与模式P的字符进行比较。该算法效率较低。

代码

class Solution {
    public int strStr(String haystack, String needle) {
        int mainLen = haystack.length();
        int subLen = needle.length();
        if(needle.equals("")) return 0;//注意模式字符串为空的情况
        for(int i=0;i<mainLen;i++){
            for(int j =0;j<subLen;j++){
                if(!(i+j<mainLen)) return -1;//主串下标超出
                if(!(haystack.charAt(i+j)==needle.charAt(j))) break;
                else if(j == subLen-1) return i;//完全匹配，返回主串下标
            }
        }
        return -1;
    }
}

算法的复杂度为O[(i-j)j]

MP算法

思路

指针不回溯，利用已得到的“部分匹配”结果，将模式向右“滑动”若干位置后继续比较。

参考下面给出的示例：
haystack ："cdnidnidsm"
needle："nidsm"
按照BF算法的思想，在比较haystack[2]和needle[0]时，两个字符相等，然而比较到haystack[5]和needle[3]的时候两个字符不等，于是回溯继续向后比较haystack[3]和needle[0]。可是既然能确定haystack[2]-haystack[4]与needle[0]-needle[2]是完全对应的。那么比较haystack[3]和needle[0]实际上相当于比较needle[1]和needle[0]。并且我们知道needle中前三个字符都是不同的。所以只需要从haystack[5]处继续跟needle[0]比较就行了。并且needle中字符的这些关系完全是一开始就可以确定的。

我们称记录模式字符串中各个字符之间关系的函数为失效函数。
失效函数的定义域是模式字符串在“失配”前匹配的字符串个数。取值j属于0~Len(P)-1

获取失效函数的方法：

失效函数的取值k满足P0P1…Pk = Pj-kPj-k+1…Pj。如果不存在这个k值，取-1。

直观的看k就是模式字符串前j个字符是否存在前k+1位等于后k+1位。

nidsm的失效函数为：

再举一个例子，caatcat的失效函数为：

得到了失效函数后，即可使用MP算法进行匹配。假设在某一轮比较中，失配的情况发生在模式P的第j位，如果j=0，进行下一轮比较时，目标指针向后移动一位，模式的起始比较地址回到P0，其他情况进行下一轮比较时，目标指针不发生回溯，而模式P的起始比较地址为j-1对应的失效函数的值+1。

当然也可以把这个值提前算出来便成为了Next()函数：

Next(7)可以用于继续匹配（可能要求找出所有匹配的子字符串）。

代码

class Solution {
    //获取next函数
    public int[] next(String needle){
        int len = needle.length();
        int i = 0;
        int j = -1;
        int[] next = new int[len+1];
        next[0] = -1;
        while(i < len){
            while( j > -1 && needle.charAt(i)!=needle.charAt(j))
                j = next[j];//j会有一个传递的效果，必须前一个i对应的j是1，下一个i对应的j才能是2。如果遇到不同的字符则j清零
            next[++i] = ++j;
        }
        return next;
    }
    public int strStr(String haystack, String needle) {
        int mainLen = haystack.length();
        int subLen = needle.length();
        if(needle.equals("")) return 0;//注意模式字符串为空的情况
        if(mainLen<subLen) return -1;
        int[] next = next(needle);
        int i = 0;
        int j = 0;

        while(j < mainLen){
            while(i>-1 && needle.charAt(i) != haystack.charAt(j))
                i = next[i];
            i++;
            j++;
            if(i >= subLen){
                return j-i;
            }
        }
        return -1;
    }
}

KMP算法

思路

在MP算法的基础上，还要避免最长前缀之后的那个字符不等于原来失配的那个字符。
下面在已知mpNext表的情况下，给出建立kmpNext表的规则。这个规则分为四种情况：

1. 如果mpNext[j] = 0且Pj = P0，则令kmpNext[j] = -1。
2. 如果mpNext[j] = 0且Pj ≠ P0，则令kmpNext[j] = 0。
3. 如果mpNext[j] ≠ 0且Pj ≠ PmpNext[j]，则令kmpNext[j] = mpNext[j]。
4. 如果mpNext[j] ≠ 0且Pj = PmpNext[j]，则用mpNext[j]的值替换原来mpNext[j]中的j值，直到情况转换为前3种情况的一种，进而递归地求解kmpNext[j]。

代码

class Solution {
    //获取kmpNext数组
    public int[] next(String needle){
        int len = needle.length();
        int i = 0;
        int j = -1;
        int[] next = new int[len+1];
        next[0] = -1;
        while(i < len-1){
            while( j > -1 && needle.charAt(i)!=needle.charAt(j))
                j = next[j];
            i++;
            j++;
            if(needle.charAt(i) == needle.charAt(j))
                next[i] = next[j];
            else
                next[i] = j;
        }
        return next;
    }

    public int strStr(String haystack, String needle) {
        int mainLen = haystack.length();
        int subLen = needle.length();
        if(needle.equals("")) return 0;//注意模式字符串为空的情况
        if(mainLen<subLen) return -1;
        int[] next = next(needle);
        int i = 0;
        int j = 0;

        while(j < mainLen){
            while(i>-1 && needle.charAt(i) != haystack.charAt(j))
                i = next[i];
            i++;
            j++;
            if(i >= subLen){
                return j-i;
            }
        }
        return -1;
    }
}