题目描述

实现 strStr() 函数。

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

样例

输入: haystack = "hello", needle = "ll"
输出: 2

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

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

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

算法1

kmp算法

• 1、ne[i]记录p[]数组中以i结尾的最大后缀等于最大前缀时的最大前缀的末尾位置
• 2、预处理出ne[]数组
• 3、枚举s[]数组，利用ne[]数组找到最大前缀长度是m的对应的最大后缀的位置i，因此[i - m,m]是当前符合条件的子串

模版题目 AcWing 831. KMP字符串

时间复杂度 $O(n + m)$

Java 代码

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() < 1) return 0;
        int m = needle.length();
        char[] p = (" " + needle).toCharArray();
        int n = haystack.length();
        char[] s = (" " + haystack).toCharArray();
        int[] ne = new int[m + 10];
        //预处理p的ne数组
        //ne[i]记录p[]数组中以i结尾的最大后缀等于最大前缀时的最大前缀的末尾位置
        for(int i = 2,j = 0;i <= m;i ++)
        {
            while(j != 0 && p[i] != p[j + 1]) j = ne[j];
            if(p[i] == p[j + 1]) j ++;
            ne[i] = j;
        }
        //匹配
        for(int i = 1,j = 0;i <= n;i ++)
        {
            while(j != 0 && s[i] != p[j + 1]) j = ne[j];
            if(s[i] == p[j + 1]) j ++;
            if(j == m)
            {
                j = ne[j];
                return i - m;
            }
        }
        return -1;
    }
}

算法2

调函数

直接枚举所有位置，调用substring函数，速度反而比算法1快（不知道为啥）

时间复杂度 $O(nm)$

Java 代码

class Solution {
    public int strStr(String s, String p) {
        if(p.length() < 1) return 0;
        int n = s.length();
        int m = p.length();
        for(int i = 0;i < n - m + 1;i ++)
        {
            if(s.substring(i,i + m).equals(p))
                return i;
        }
        return -1;
    }
}