力扣-28题实现strStr()（C++）- 字符串匹配+KMP算法

朴灿烈づ我的快乐病毒、 2022-09-11 04:17 181阅读 0赞

题目链接：[https://leetcode-cn.com/problems/implement-strstr/][https_leetcode-cn.com_problems_implement-strstr]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
思路：  
![在这里插入图片描述][6bbd0209622b4b19bd08c2e6b11644e7.gif]

class Solution {
        
    public:
        void getNext(int* next,const string& s){
        
            int j=0;//j是在前缀表(next数组)中的元素数值
            next[0]=0;
    
            for(int i=1;i<s.size();i++){
        //这个while和下面的if不能互换位置
                while(j>0&&s[i]!=s[j]){
        //前后缀不相同，则就取前一个next的数值，向前回退
                    j=next[j-1];
                }
    
                if(s[i]==s[j]){
        //前后缀相同
                    j++;
                }
                
                next[i]=j;//将j(前缀的长度)赋给next[i]
            }
        }
    
        int strStr(string haystack, string needle) {
        
            if(needle.size()==0) return 0;
    
            int next[needle.size()];
            getNext(next,needle);
    
            int j=0;//对应needle的下标
            for(int i=0;i<haystack.size();i++){
        
                while(j>0&&haystack[i]!=needle[j]){
        //这个while和下面的if不能互换位置
                    j=next[j-1];
                }
    
                if(haystack[i]==needle[j]){
        
                    j++;
                }
    
                if(j==needle.size()){
        
                    return (i-needle.size()+1);
                }
            }
    
            return -1;
        }
    };

[https_leetcode-cn.com_problems_implement-strstr]: https://leetcode-cn.com/problems/implement-strstr/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/63385951c7be4972b8817b9228f2e886.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/2b9b9733f5a241a48e820b5b37f27d30.png
[6bbd0209622b4b19bd08c2e6b11644e7.gif]: /images/20220828/d4bcb73b181c4ec294dac0ff2ce44048.png