problem:

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

此题目实质为字符串匹配问题，其中比较高效的算法是KMP算法 它相对于暴力破解算法比较成功的找到了有效的回溯位置。

解法一：暴力破解

1 class Solution { 2 public: 3     int strStr(string haystack, string needle) { 4         int slen=haystack.size(); 5         int plen=needle.size(); 6          7         int i=0; 8         int j=0; 9         for(;i
     

 解法二：kmp

1 class Solution { 2 public: 3     int strStr(string s, string p) { 4         //kmp算法 5          6         if(!p.size()||!s.size()) return 0; 7         vector
     
       next(p.size(),0); 8         int plen=p.size(); 9         int slen=s.size();10         computeNext(next,p,plen);11         int j;int i;12         for(i=0;i
      

&next,string &p,int &plen)31 {32 33 int q=next[0]=-1;34 35 int j=0;36 plen--;37 while(j