Facebook: Implement strstr using KMP

rt， 有人用双重循环做， 考官不满意，所以还是练练KMP写法吧， 不难

facebook 要问这种题就是存心不想要人过面试

用KMP？？也只有facebook想的出来。。没点竞赛背景不行啊。过两天复习下KMP来写写

直接叫15分钟写个B+树得了

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int KMP (string str, string p, vector<int> next)
{
     int j = -1;
     for (int i = 0; i < str.size(); ++i)
     {
          while(j >= 0 && str[i] != p[j + 1])
               j = next[j];
          if (str[i] == p[j + 1])
               ++j;
          if (j == p.size() - 1)
               return i - p.size();
     }
     return -1;
}

vector<int> getNext(string p)
{
     vector<int> v(p.size());
     int j = -1;
     v[0] = -1;
     for(int i = 1; i < p.size(); ++i)
     {
          while(j >= 0 && p[j + 1] != p[i])
               j = v[j];
          if (p[i] == p[j + 1])
               ++j;
          v[i] = j;
     }
     return v;
}

char* strstr(char* haystack, char* needle)
{
     string str(haystack);
     string pattern(needle);

     vector<int> next = getNext(pattern);
     int r = KMP(str, pattern, next);
     if (r == -1)
          return 0;
     return haystack + r;
}

int main()
{
     char* h = "asdfasdf";
     char* n = "fasd";
     cout << strstr(h, n) << endl;
}

真难啊。。。。。。

回复 4# wwwyhx
再写个AVL, 红黑什么的吧

KMP还好吧。知道怎么回事就能写出来。

KMP还好吧。知道怎么回事就能写出来。
nooneknow 发表于 2011-11-5 10:12

    忘了咋整