LeetCode OJ:Implement strStr()

本文主要是介绍LeetCode OJ:Implement strStr()，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法思想：

循环扫描，比较直白

class Solution {
public:char *strStr(char *haystack, char *needle) {int size = strlen(haystack) - strlen(needle);for (int i = 0; i <= size; i++) {  bool flag = true;  for (int j = 0; j < strlen(needle); j++) {  if (haystack[i + j] != needle[j]) {  flag = false;  break;  }  }  if (flag == true) {  return &haystack[i];  }  }  return NULL;  }
};

2、简单匹配算法BF算法

class Solution {
public:char *strStr(char *haystack, char *needle) {int slen = strlen(haystack);int tlen = strlen(needle);int i = 0 ,j = 0;while ( i+j < slen && j < tlen){if ( haystack[i+j] == needle[j] ){j ++;}else{i ++;j = 0;}}if ( j >= tlen)return &haystack[i];elsereturn NULL;}
};

3、KMP算法

KMP算法

class Solution {
public://代码4-1    //修正后的求next数组各值的函数代码    void get_nextval(char const* ptrn, int plen, int* nextval)    {    int i = 0;     nextval[i] = -1;    int j = -1;    while( i < plen-1 )    {    if( j == -1 || ptrn[i] == ptrn[j] )   //循环的if部分    {    ++i;    ++j;    if( ptrn[i] != ptrn[j] )     nextval[i] = j;          else    nextval[i] = nextval[j];    }    else                                     j = nextval[j];    }    }char *strStr(char *haystack, char *needle) {int slen = strlen(haystack);int tlen = strlen(needle);int i = 0 ,j = 0;int *nextval=new int[tlen];get_nextval(needle,tlen,nextval);while ( i+j < slen && j < tlen){if ( j == -1 || haystack[i+j] == needle[j] ){j ++;}else{i ++;j = nextval[j];}}if ( j >= tlen)return &haystack[i];elsereturn NULL;}
};

这篇关于LeetCode OJ:Implement strStr()的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---