LeetCode 28. Implement strStr()

Problem

LeetCode 28. Implement strStr()

1. 题目简述

给出两个字符串haystack和needle，找出needle在haystack中出现的首次位置，如果没有出现则返回-1。needle为空的时候返回0，例如：

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

2. 算法思路

2 pointers暴力搜索

两个指针分别指向s1和s2，如果遇到不匹配，则将s2的指针重置，s1指针向后移动一位。

KMP算法

KMP算法的详解可以参考：

1. 花花酱的KMP算法视频
2. 某大佬的blog

或者这篇字符串汇总的Blog中：传送门

3. 解法

2 pointers

class Solution {
    public int strStr(String haystack, String needle) {
        int h = haystack.length(), n = needle.length();
        if (n == 0) {
            return 0;
        }
        if (n > h) {
            return -1;
        }

        int p1 = 0, p2 = 0;
        while (p1 < h - n + 1) {
            int currLen = 0;
            while (p1 < h && p2 < n && haystack.charAt(p1) == needle.charAt(p2)) {
                p1++;
                p2++;
                currLen++;
            }

            if (currLen == n) {
                return p1 - n;
            } else {
                p1 = p1 - currLen + 1;
                p2 = 0;
            }
        }

        return -1;
    }
}

KMP字符型匹配算法

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

        int[] next = buildKMPTable(needle);
        for (int i = 0, j = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                // 这里不一定是要返回，也可以继续搜索，直接记录个什么数，然后j继续跳回去
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    // 这个是大重点！！！KMP表的实现
    private int[] buildKMPTable(String s) {
        int length = s.length();
        int[] next = new int[length + 1];
        for (int i = 1, j = 0; i < length; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i + 1] = j;
        }
        return next;
    }
}