[力扣_28] 实现 strStr()

题目入口:点击进入

相关算法:

  • KMP算法,时间复杂度——O(n),空间复杂度O(M)【M为模式串的长度】

思路和算法:

这题其实一看就是KMP算法,关于KMP在串的那一数据结构章节我有很详细就笔记,在次看到相关体型,我去了解了下JAVA中indexOf方法:查看KMP与indexOF的区别所在

可能我的笔记更适合我看吧,我发现其他题解中对KMP的讲解我看着思路越理越乱,所以在这里我放上我笔记的传送门:点击进入

代码如下所示:

int*next_arr(char *s)
{
   int sleng=strlen(s);
   int *next=(int*)malloc(sizeof(int)*(sleng+1));
   int k=-1,j=0;
   next[0]=-1;
   while(j<sleng)
   {
       if(k==-1||s[k]==s[j])
       {
           k++;j++;
           next[j]=k;
       }
       else
       {
           k=next[k];
       }
   }
   return next;
}
int strStr(char * haystack, char * needle){
   if(!haystack||!needle) return 0;
   int i=0,j=0;
  
   int Slen=strlen(haystack);
   int slen=strlen(needle);
   int *next=next_arr(needle);

   while(i<Slen&&j<slen)
   {
       if(j==-1||haystack[i]==needle[j])
       {
           i++;j++;
       }
       else{
          j=next[j];
       }
   }
   if(j>=slen) return i-j;
   else return -1;

}

本文链接:

https://nullcode.fun/75.html
1 + 2 =
快来做第一个评论的人吧~