LeetCode28 实现strStr()

题目描述

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

样例

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

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

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

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

算法分析

kmp算法

kmp下标从一开始，方便计算

kmp的关键就是next数组

next[i]是所有p[1~i]的前缀和后缀(相等)的长度的最大值；

• 怎么使用next[i]

• 怎么求next[j]
• 求的时候，就把第一个看成p就可以了
• 枚举s[]数组，利用ne[]数组找到最大前缀长度是m的对应的最大后缀的位置i，因此[i - m,m]是当前符合条件的子串

时间复杂度

$O(n+m)$

Java代码

class Solution {
    public int strStr(String haystack , String needle ) {
        if(needle .length() < 1) return 0;

        int n = haystack.length();
        int m = needle .length();
        haystack = " " + haystack;
        needle = " " + needle;

        char[] s = haystack.toCharArray();
        char[] p = needle.toCharArray();

        int[] ne = new int[m+10];

        //初始化ne输出
        //ne[1]=0
        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){
                return i - m;
            }
        }

        return -1;


    }
}