面试题30：KMP 字符串查找

参考：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
自己写的很简单的KMP字符串匹配

 int KMP(string s,string p){

     int pLen = p.length();

     int* next = new int[pLen];

     next[] = -;

     int k = -;

     int j = ;

     while(j < pLen - ){

         if(k == - || p[k] == p[j]){

             k++;

             j++;

             next[j] = k;

         }else{

             k = next[k];

         }

     }

     //print next array;

     for(int k=;k<pLen;k++){

         std::cout << next[k]<< ",";

     }

     std::cout << std::endl;

     j = ;

     size_t i = ;

     size_t sLen = s.length();

     while(i<sLen && j < pLen){

         if(j == - || s[i] == p[j]){

             i++;

             j++;

         }else{

             j = next[j];

         }

     }

     delete next;

     if(j == pLen){

         return i - j;

     }else{

         return -;

     }

 }

Implement strStr().

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

 class Solution {

 public:

     char *strStr(char *haystack, char *needle) {

         if(haystack == nullptr || needle == nullptr) return nullptr;

         int i = ,j =;

         int start = ;

         while(haystack[i] != '\0' && needle[j] != '\0'){

             if(haystack[i] == needle[j]){

                 i++;

                 j++;

             }else{

                 start++;

                 i = start;

                 j = ;

             }

         }

         if(needle[j] == '\0') return haystack+start;

         else return nullptr;

     }

 };

巴特西

面试题30：KMP 字符串查找

最新文章

热门文章