28. Implement strStr()

Implement strStr().

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

判断子串needle 在主串haystack中首次出现的位置

C++（6ms）： KMP算法

 1 class Solution {
 2 public:
 3     vector<int> getNext(string needle , int tlen){
 4         int j, k;
 5         vector<int> Next(tlen+1, 0);
 6         j = 0; k = -1; Next[0] = -1;
 7         while(j < tlen)
 8             if(k == -1 || needle[j] == needle[k])
 9                 Next[++j] = ++k;
10             else
11                 k = Next[k];
12         return Next ;
13     }
14     
15     int strStr(string haystack, string needle) {
16         int slen = haystack.size() ;
17         int tlen = needle.size() ;
18         if (!tlen)
19             return 0 ;
20         vector<int> Next = getNext(needle,tlen) ;
21         int i = 0, j = 0;
22         while(i < slen && j < tlen)
23         {
24             if(j == -1 || haystack[i] == needle[j])
25             {
26                 i++; j++;
27             }
28             else
29                 j = Next[j];
30         }
31         if(j == tlen)
32             return i - tlen ;
33         else
34             return -1;
35     }
36 };