LeetCode 28. 实现 strStr()

野性酷女 2022-10-31 04:24 97阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//解法一：双指针  55%
    public int strStr(String haystack, String needle) {
        
        int m = haystack.length(), n = needle.length();
        if (n == 0) return 0;
        for (int i = 0; i <= m - n; i++) {
        
            for (int j = 0; j < n; j++) {
        
                if (haystack.charAt(i + j) != needle.charAt(j)) break;
                if (j == n - 1) return i;
            }
        }
        return -1;
    }

//解法二：KMP算法
    //https://leetcode-cn.com/problems/implement-strstr/solution/kmp-suan-fa-xiang-jie-by-labuladong/
    class KMP{
        
        private int[][] dp;
        private String pat;
    
        public KMP(String pat){
        
            this.pat = pat;
            int M = pat.length();
            dp = new int[M][256];
            dp[0][pat.charAt(0)] = 1;
            int X = 0;
            for(int j = 1; j < M; j++){
        
                for(int c = 0; c < 256; c++){
        
                    if(pat.charAt(j) == c)
                        dp[j][c] = j + 1;
                    else
                        dp[j][c] = dp[X][c];
                }
                X = dp[X][pat.charAt(j)];
            }
        }
    
        public int search(String txt){
        
            int M = pat.length();
            int N = txt.length();
            int j = 0;
            for(int i = 0; i < N; i++){
        
                j = dp[j][txt.charAt(i)];
                if(j == M)
                    return i - M + 1;
            }
            return -1;
        }
    }
    class Solution {
        
        public int strStr(String haystack, String needle) {
        
            if(needle.length() == 0)
                return 0;
            KMP kmp = new KMP(needle);
            return kmp.search(haystack);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/9dbffb577cb545e3923a5b65ff29a664.png