Problem: 28. 找出字元串中第一個匹配項的下標

• 解題方法
• 思路
  • 構建next數組
  • 回溯查找
• 複雜度
• Code

解題方法

1. 構建next串
2. 回溯查找next串,最後下標

思路

1. 通過最大首碼尾碼能找到下一次未查找到後要回溯的位置

構建next數組

無論如何第一個數的下一次回溯位置肯定是0,因此next[0]=0
這裡的 j表示首碼起始位置 i表示尾碼起始位置
如果找到字元不相同到的話,就讓他一直回溯找,並且回溯賦值j = next[j-1]
能找到相同字元的話就直接i++,j++,並且把next[i] = j
這裡先寫while判斷不相同 後寫相同,是因為不相同的終點
一定是有相同的尾碼或者直接結束查找(到了字元串末尾)

回溯查找

其實和上面的思路差不多,不能查找相同字元就一直回溯,能的話就共同前進,直到j到了模式串長度
這時因為i也在前進,所以i的下標是 應該返回的下標+(匹配串的長-1)

複雜度

時間複雜度:

添加時間複雜度, 示例： $O(m+n)$

空間複雜度:

添加空間複雜度, 示例： $O(m)$

Code

class Solution {

    public int strStr(String haystack, String needle) {
        return new KMP(needle).search(haystack);
    }

    public class KMP {
        private String pattern;   // 模式串
        private int[] next;
        public KMP(String pattern){
            this.pattern = pattern;
            int m = pattern.length();
            // 創建next 數組
            next = new int[m];
            next[0] = 0;
            for(int i = 1,j=0; i < m; i++){
                while(j>0&&pattern.charAt(i)!=pattern.charAt(j)){
                    j = next[j-1];
                }
                if(pattern.charAt(i) == pattern.charAt(j)){
                    j++;
                }
                next[i] = j;
            }
        }

        public int search(String text){
            int j = 0;
            for(int i=0;i<text.length();i++){
                while(j>0&&text.charAt(i) != pattern.charAt(j)){
                    j = next[j-1];
                }
                if(text.charAt(i) == pattern.charAt(j)){
                    j++;
                }
                if(j == pattern.length()){
                    return i-pattern.length()+1;
                }
            }
            return -1;
        }
    }

}