(KMP) leetcode 28. Implement strStr() 字符串匹配

拼搏现实的明天。 2021-10-01 06:20 259阅读 0赞

**![1266918-20190727220348758-219099188.png][]**

思路一：暴力遍历（两重循环会超时==）

class Solution {
    public:
        int strStr(string haystack, string needle) {
            int h = haystack.size();
            int n = needle.size();
            if(needle.empty())
                return 0;
            for(int i=0; i< h - n +1; ++i){
                if(haystack.substr(i, n) == needle)
                    return i;
            }
            return -1;
        }
    };

思路：kmp算法。

参考链接：

[https://www.youtube.com/watch?v=3IFxpozBs2I&t=4s][https_www.youtube.com_watch_v_3IFxpozBs2I_t_4s]

class Solution {
    public:
        void prefix_table(string pattern, int prefix[], int n){
            //表长为n，pattern为要计算前后缀的字符串
            prefix[0] = 0;  
            int len = 0, i=1;  //i从索引为1处开始比较
            while(i<n){
                if(pattern[i] == pattern[len]){
                    len ++;
                    prefix[i] = len;
                    i++;
                }
                else{
                    if(len>0)
                        len = prefix[len-1];
                    else{
                        prefix[i]=0;
                        i++;
                    }
                        
                }  
            }
        }
        
        void move_prefix_table(int prefix[], int n){
            
            for(int i=n-1; i>0; --i)
                prefix[i] = prefix[i-1];
            prefix[0] = -1;
        }
        
        
        int strStr(string haystack, string needle) {
            int n = needle.size(), m = haystack.size();
            if(n ==0)
                return 0;
            if(m < n)
                return -1;
            int prefix[n+1];
            prefix_table(needle, prefix, n);
            move_prefix_table(prefix, n);
            int i=0, j=0; 
            //haystack[i] , m
            //needle[j] , n
            while(i<m){
                if(j == n-1 && haystack[i] == needle[j]){
    
                }
                if(haystack[i] == needle[j]){
                    if(j == n-1)
                        return i-j;   //j = prefix[j];
                    else{
                        i++;
                        j++;
                    }
                }
                else{
                    j = prefix[j];
                    if(j==-1){
                        i++;
                        j++;
                    }
                }
            }
            return -1;
        }
    };

转载于:https://www.cnblogs.com/Bella2017/p/11256984.html

[1266918-20190727220348758-219099188.png]: /images/20210724/ee9bfedb0bdd4a17ba39543f44953d69.png
[https_www.youtube.com_watch_v_3IFxpozBs2I_t_4s]: https://www.youtube.com/watch?v=3IFxpozBs2I&t=4s