28.找出字符串中第一个匹配项的下标

模拟

最直接的做法就是枚举主串中每一个可能作为起点的位置，然后判断从这里开始能否完整匹配 needle。

如果当前位置开始的每个字符都和 needle 对应位置相同，那么就返回这个起点下标；否则继续尝试下一个位置即可。

时间复杂度 $O(nm)$

空间复杂度 $O(1)$

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return -1;
        }
        for (int i = 0; i < haystack.length() - needle.length() + 1; ++i) {
            if (check(haystack, i, needle)) {
                return i;
            }
        }
        return -1;
    }

    private boolean check(String haystack, int start, String needle) {
        if (haystack.length() - start + 1 < needle.length()) {
            return false;
        }
        for (int i = 0; i < needle.length(); ++i) {
            if (haystack.charAt(start + i) != needle.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

KMP

朴素匹配在失配时会回退主串指针，很多比较其实是重复的。KMP 的核心就在于，失配后不回退主串，而是利用模式串自身的信息，直接把模式串滑到一个合适位置继续匹配。

具体来说，先为模式串预处理出 next 数组，表示当某个位置失配时，模式串指针下一步应跳到哪里。这样在匹配过程中，一旦字符不同，就可以快速跳过不可能匹配的部分，从而把总时间复杂度优化到 $O(n + m)$。

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

空间复杂度 $O(m)$

class Solution {
    public int strStr(String haystack, String needle) {
        return kmp(haystack, needle);
    }
    
    private int kmp(String target, String pattern) {  // 时间复杂度：O(n + m)
        int n = target.length();      // 主串长度
        int m = pattern.length();     // 模式串长度

        // 边界情况处理
        if (m == 0) {                 // 空模式串
            return 0;
        }
        if (n < m) {                  // 主串比模式串短，不可能匹配
            return -1;
        }
        
        // 1. 计算模式串的next数组（部分匹配表）
        int[] next = getNext(pattern);
        
        // 2. 进行KMP匹配
        int i = 0;  // 主串指针
        int j = 0;  // 模式串指针
        
        while (i < n && j < m) {
            // 情况1：模式串第一个字符就匹配失败（j=-1），或者当前字符匹配成功
            if (j == -1 || target.charAt(i) == pattern.charAt(j)) {
                i++;  // 主串指针后移
                j++;  // 模式串指针后移
            } 
            // 情况2：字符不匹配，根据next数组跳转模式串指针
            else {
                j = next[j];  // 模式串指针回退到next[j]位置
            }
        }
        
        // 匹配结果判断
        if (j == m) {          // 模式串完全匹配成功
            return i - j;      // 返回匹配的起始索引
        } else {               // 匹配失败
            return -1;
        }
    }
    
    private int[] getNext(String pattern) {  // 时间复杂度：O(m)
        int n = pattern.length();      // 模式串长度
        int[] next = new int[n];       // 创建next数组
        next[0] = -1;                  // 初始值，表示模式串第一个字符匹配失败时需要特殊处理
        
        int i = 0;  // 后缀末尾指针
        int j = -1; // 前缀末尾指针（初始为-1，表示无前缀）
        
        // 构建next数组，注意循环条件是 i < n-1
        while (i < n - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;  // 模式串指针后移
                j++;  // 已匹配的前缀长度增加
                next[i] = j;
            } else {// j 回退，但回退次数小于等于前进次数即i增加量（if分支中二者同步增加i意味着j增加了多少次）
                j = next[j];  // 利用已计算的next值进行回退
            }
        }
        return next;
    }
}