leetcode Implement strStr()

KMP算法：

/** KMP算法中获取模式中每位的next值。next[i]=j表示pattern[0..i]中最长前后缀后面的那个元素的位置为j在进行匹配的过程中，匹配失败则取得上一个 next 函数的值*/

void get_next(char *pattern, int *next)
{
 int length=strlen(pattern);//模式的总长度
 next[0]=0;//第一个位置一定为0
 int j=0;//匹配的起始位置
 for(int i=1;i<length;i++)//获取next的其他位的值
 {
  //如果已经匹配上了某些字符，但是当前无法匹配，回溯寻找
  while(j>0&&pattern[i]!=pattern[j])
  {
   j=next[j-1];//在j位匹配失败，那么就从位置next[j-1]开始匹配
               //next[j-1]表示pattern[0..j-1]中最长前后缀后面的那个元素
  }
  //如果能够匹配上，向下推进一个位置，表示在位j上匹配成功后，下一个需要考虑的位是j+1
  if(pattern[j]==pattern[i])
   j++;
  next[i]=j;
 }
}

char *strStr(char *haystack, char *needle) {
 if(haystack==NULL||needle==NULL)
  return NULL;
 if(needle[0]==‘\0‘)
  return haystack;
 int length1=strlen(haystack);
 int length2=strlen(needle);
 int *next=new int[length2];
 get_next(needle,next);
 int j=0;
 for(int i=0;i<length1;i++)
 {
  //j位置跳到next[j-1],
  //next[j-1]中存储的是pattern[0..j-1]中最长前后缀后面的元素的位置
  while(j>0&&haystack[i]!=needle[j])
   j=next[j-1];
  //匹配成功，j往后移一位
  if(haystack[i]==needle[j])
   j++;
  //全部匹配，返回开始位置
  if(j==length2)
   return haystack+i-length2+1;
 }
 //没找到，返回NULL
 return NULL;
}

leetcode Implement strStr(),布布扣,bubuko.com

leetcode Implement strStr()

原文：http://www.cnblogs.com/myyan/p/3880364.html