🌕🌕🌕🌕 28. 实现 strStr()

难度: 🌕🌕🌕🌕

问题描述

---

解法 1 - 普通遍历

class Solution {
    public int strStr(String haystack, String needle) {
        // 思路：
        // 遍历，找到满足条件的，继续判断剩下的字符是否匹配
        int m = haystack.length();
        int n = needle.length();
        // 特殊情况特判
        if(n == 0) {
            return 0;
        }
        // n > 0
        if(m < n) {
            return -1;
        }
        // m >= n
        for(int i = 0; i <= m - n; i ++) {
            String cur = haystack.substring(i, i + n);
            if(cur.equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}

---

输出 1

---

解法 2 - KMP

class Solution {
    // 前缀和：不包含 index 在内的前面的字符串
    // 后缀和：不包含 0 在内的字符串
    // 例： aabaaf
    // 0 0
    // 1 a, a = 1
    // 2 aa, ab = 0
    // 3 aab, aba = 1
    // 4 aaba, abaa = 2
    // 5 aabaa, abaaf = 0
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        char[] mm = haystack.toCharArray();
        char[] nn = needle.toCharArray();
        if(n == 0) {
            return 0;
        }
        if(m < n) {
            return -1;
        }
        return kmp(mm, m, nn, n);
    }

    private int kmp(char[] mm, int m, char[] nn, int n) {
        // 首先获取 nn 的前缀和数组
        int[] array = getArray(nn, n);
        int j = 0;
        for(int i = 0; i < m; i ++) {
            while(j > 0 && mm[i] != nn[j]) {
                j = array[j - 1];
            }
            if(mm[i] == nn[j])
                j ++;
            if(j == n)
                return i-n + 1;
        }
        return -1;
    }

    private int[] getArray(char[] array, int len) {
        if(len == 1) {
            return new int[] {0};
        }
        int[] res = new int[len];
        int left = 0;
        int right = 1;
        res[0] = 0;
        for(; right < len; right ++) {
            while(left > 0 && array[left] != array[right]) {
                left = res[left - 1]; // 回退
            }
            if(array[left] == array[right]) {
                left ++;
            }
            res[right] = left;
        }
        return res;
    }
}

---

输出 2