实现strStr()

LeetCode题目，28. Implement strStr()

先看题目描述

大意就是给定一个 haystack 字符串和一个 needle 字符串，让我们在 haystack 字符串中找出 needle 字符串出现的第一个位置，如果不存在，则返回 -1

算法和思路

这题是一道典型的子串匹配问题，解决子串匹配问题比较经典的算法有 KMP算法，Sunday算法等，核心思路就是尽量增大模式串的移动步数，核心思路是这个，具体实现看下面代码吧，下面的代码实现的是 Sunday 算法

算法和源码

Sunday算法

class Solution {
    public int strStr(String haystack, String needle) {
        int n = needle.length();
        if (n == 0) {
            return 0;
        }
        int m = haystack.length();
        if (m < n) {
            return -1;
        }
        char[] hs = haystack.toCharArray();
        char[] ns = needle.toCharArray();
        int[] offest = new int[26];
        for (int i = 0; i < 26; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (ns[j] - 'a' == i) {
                    offest[i] = n - j;
                    break;
                }
            }
        }
        int start = 0;
        while (start <= m - n  && hs[start] != ns[0]) {
            start++;
        }
        while (start <= m - n) {
            int i = 0;
            for (; i < n; i++) {
                if (hs[i + start] != ns[i]) {
                    break;
                }
            }
            if (i == n) {
                return start;
            }
            int index = start + n;
            if (index >= m) {
                return -1;
            }
            char c = hs[index];
            if (offest[c - 'a'] > 0) {
                start += offest[c - 'a'];
            } else {
                start = index + 1;
                while (start <= m - n && hs[start] != ns[0]) {
                    start++;
                }
            }
        }
        return -1;
    }
}

因为这道题我第一反应是拿 Sunday 算法做，然后手写了个 Sunday 算法提交的，所以我还疑惑这题为什么是个简单题，后来看了别人的代码，发现可以直接调用内置函数，嗯那么这确实是道简单题

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