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

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

在算法学习的道路上，每天解决一道算法题不仅能提升编码思维，还能增强解决问题的能力。今天，让我们一起来学习LeetCode第28题：找出字符串中第一个匹配项的下标。这道题目虽然标记为简单，但其中蕴含的KMP算法思想却非常巧妙，值得我们深入研究。

题目分析

这道题目要求实现一个功能，类似于Java中String的indexOf方法，即在字符串s中查找子串t的第一个匹配位置。最直观的解法是暴力匹配，但这并不是最优解。让我们先从暴力解法开始分析。

假设原始字符串s为aabaacaadaae，目标字符串t为aacaad，暴力解法的匹配过程如下：

可以看到，暴力解法的时间复杂度为O(m*n)，其中m和n分别是两个字符串的长度。那么，有没有更高效的解法呢？答案是肯定的，这就是KMP算法。

KMP算法简介

KMP算法的核心思想是利用前缀表来避免不必要的回溯。前缀表记录了目标字符串中每个位置的最长相同前后缀长度。例如，对于目标字符串aacaad，其前缀表如下：

从图中可以看出，通过前缀表可以避免重复匹配已经匹配过的部分，从而提高效率。

代码实现

暴力解法

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            if(haystack.charAt(i) != needle.charAt(0)) {
                continue;
            }
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}

KMP算法

class Solution {
    // 获取前缀表
    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        // 下面逻辑，找以i下标结尾的字符的最长公共前后缀，并且从第二个字符开始查找
        for (int i = 1; i < s.length(); i++) {
            // 前后缀不相等 不断回溯
            while (j > 0 && s.charAt(j) != s.charAt(i)) 
                j = next[j - 1];
            // 连续相同，相等前缀自增 不断往前累加
            if (s.charAt(j) == s.charAt(i)) 
                j++;
            next[i] = j; 
        }
    }
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        // 构造前缀表
        getNext(next, needle);
        int j = 0;
        // 往前遍历原始数组
        for (int i = 0; i < haystack.length(); i++) {
            // 遇到了不相同的，查找前缀表
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];
            // 连续相等，相等前缀+1
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;
    }
}

总结

KMP算法通过构建前缀表，显著提高了字符串匹配的效率，避免了不必要的回溯。虽然KMP算法的理解有一定难度，但通过多实践和研究，可以掌握这一强大的算法技巧。算法学习是一个循序渐进的过程，希望这篇文章能帮助你更好地理解字符串匹配问题的解法。