解法一：Brute-force

1 int strStr(string haystack, string needle) 2 { 3     int m = haystack.size(); 4     int n = needle.size(); 5     if (!n)  6         return 0; 7     for (int i = 0; i < m - n + 1; ++i) { 8         int k = i, j = 0; 9         while (j < n) {10             if (needle[j] == haystack[k]) {11                 j++;12                 k++;13             } else {14                 break;15             }16         }17         if (j == n)18             return i;19     }20     return -1;21 }

解法二：KMP

1 vector
     
       GetNext(const string& T) 2 { 3     int len = T.size(); 4     vector
      
        next(len, 0); 5     for (int i = 1, k = 0; i < len;) { 6         if (T[i] == T[k]) 7             next[i++] = ++k; 8         else if (k) 9             k = next[k - 1];10         else11             next[i++] = 0;12     }13     return next;14 }15 16 int strStr(string haystack, string needle)17 {18     int m = haystack.size();19     int n = needle.size();20     if (n == 0)21         return 0;22     23     vector
       
         next = GetNext(needle);24     for (int i = 0, j = 0; i < m;) {25         if (haystack[i] == needle[j]) {26             i++;27             j++;28         }29         if (j == n)30             return i - n;31         if (i < m && haystack[i] != needle[j]) {32             if (j)33                 j = next[j - 1];34             else35                 i++;36         }37     }38     return -1;39 }