LeetCode 28.实现strStr()

实现strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

方法：KMP算法

算法思路：

1. 构建next数组。next数组是前缀表，记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

   

   int i = 1;    //i，j两个指针
   int j = 0;
   int[] next = new int[n];
   while (i < n) {
               if (needle.charAt(i) != needle.charAt(j) && j != 0) {
                   j = next[j - 1];    //当i，j指针所指不相等，且j ！= 0，则j跳到前一位记录的下标
               } else if (needle.charAt(i) != needle.charAt(j) && j == 0) {
                   next[i] = 0;				//当i，j指针所指不相等，且j == 0，记录next[i] = 0
                   i++;
               } else if (needle.charAt(i) == needle.charAt(j)) {
                   next[i] = j + 1;    //当i，j指针所指相等，记录next[i] = j + 1，i和j后移一位
                   i++;
                   j++;
               }
           }

2. 根据next数组遍历hayStack和needle字符串。

   

代码实现：

class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        int i = 1;
        int j = 0;
        int[] next = new int[n];
        while(i < n){
            if(needle.charAt(i) != needle.charAt(j) && j != 0){
                j = next[j - 1];
            }else if(needle.charAt(i) != needle.charAt(j) && j == 0){
                next[i] = 0;
                i++;
            }else if(needle.charAt(i) == needle.charAt(j)){
                next[i] = j + 1;
                i++;
                j++;
            }
        }
        int b = 0;
        for(int a = 0; a < haystack.length(); a++){
            while(haystack.charAt(a) != needle.charAt(b) && b > 0){
                b = next[b - 1];    //当a，b指针所指不相等，且b ！= 0，则b跳到前一位记录的下标
            }
            if(haystack.charAt(a) == needle.charAt(b)){
                b++;				//当a，b指针所指相等，a和b后移一位
            }
            if(b == needle.length()){
                return a - needle.length() + 1;				//当遍历完needle，说明找到相等子串，返回
            }
        }
        return -1;
    }
}

参考

代码随想录 - 实现strStr