当前位置：首页 > news >正文

[LeetCode]—Implement strStr() 寻找子串匹配第一个位置（KMP）

news 来源：原创 2024/5/4 15:00:32

Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

分析:

子串匹配问题。主要用该题巩固复习了一下KMP算法。

先用BF方法，快速的完成一下:复杂度O(M*N)

class Solution {
public:
     char *strStr(char *haystack, char *needle) {
        int lh=strlen(haystack);
        int ln=strlen(needle);
        
         int i=0,j=0,start;
         if (ln==0)return haystack; 
         while((lh-i)>=ln){
            
          start=i;
          while(haystack[i++]==needle[j++]){
            if(j==ln)return &haystack[start];
          }
           i=start+1;
           j=0;
         }
         
         return NULL;
    }
};

再回去复习一下KMP算法：

KMP算法的主要贡献在于：对目标串S的遍历可以一次到底，不用再进行回溯，只移动模式串T。

主要依据:分析模式串T的自身特点，如果前缀和后缀有相等的部分，那么，在不等的情况下，只需要移动到前缀后一位和当前目标串S当前位比较。其中求数据Next[i] 是关键。Next[i] 数组表示对于模式串T，当前i位如果未匹配成功，就让Next[i]（小于i的）位来匹配，相当于T移动。

介绍KMP详细原理的文章有：http://blog.csdn.net/v_july_v/article/details/7041827

求解Next[]数组方法清晰的文章有：http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html

最后是我实现的KMP版本的求解：O(M+N)

class Solution {
public:
     char *strStr(char *haystack, char *needle) {
            if(strlen(needle)==0)return haystack; 
            int ind=KMP(haystack,needle);
            if(ind>0)return &haystack[ind-1];
            return NULL;
      } 

private:
    int KMP(const char *S,const char *T){ //返回的是位置，不是下标
        int len_S=strlen(S);
        int len_T=strlen(T);
        int i=0,j=0;
        
        int *next=(int *)malloc(sizeof(int)*len_T);
        Next(next,T);
        
        while(i<len_S && j<len_T ){
            if(j==-1 || S[i]==T[j])
                i++,j++;
            else
                j=next[j];
        }

        if(j>=len_T) 
                return (i-len_T+1);
        else
                return -1;

    }

    void Next(int *next,const char *T){
         int len_T=strlen(T);
          assert(len_T>0);   //len_T=0,退出
         
         next[0]=-1;
         int i=0,k=-1;
         while(i<len_T-1)
         {
            if(k==-1 || T[i]==T[k]){
                k++;
                i++;
                next[i]=k;
            }else
                k=next[k];
         } 
    }
    
};

求next数组是可以由优化的，有时间也还可以继续研究下 Boyer-Mooer算法和Rabin-Karp算法。