Well, the problem does not aim for an advanced algorithm like KMP but only a clean brute-force algorithm. So we can traverse all the possible starting points of haystack (from 0 tohaystack.length() - needle.length()) and see if the following characters in haystack match those of needle.
The code is as follows.
1 class Solution { 2 public: 3 int strStr(string haystack, string needle) { 4 int m = haystack.length(), n = needle.length(); 5 if (!n) return 0; 6 for (int i = 0; i < m - n + 1; i++) { 7 int j = 0; 8 for (; j < n; j++) 9 if (haystack[i + j] != needle[j]) 10 break; 11 if (j == n) return i; 12 } 13 return -1; 14 } 15 };
Of course, you may challenge yourself implementing the KMP algorithm for this problem.
KMP is a classic and yet notoriously hard-to-understand algorithm. However, I think the following two links give nice explanations. You may refer to them.
- KMP on jBoxer's blog;
- KMP on geeksforgeeks, with a well-commented C code.
I am sorry that I am still unable to give a personal explanation of the algorithm. I only read it from the two links above and mimic the code in the second link.
My accepted C++ code using KMP is as follows. Well, it also takes 4ms -_-
1 class Solution { 2 public: 3 int strStr(string haystack, string needle) { 4 int m = haystack.length(), n = needle.length(); 5 if (!n) return 0; 6 vector<int> lps = kmpProcess(needle); 7 for (int i = 0, j = 0; i < m; ) { 8 if (haystack[i] == needle[j]) { 9 i++; 10 j++; 11 } 12 if (j == n) return i - j; 13 if (i < m && haystack[i] != needle[j]) { 14 if (j) j = lps[j - 1]; 15 else i++; 16 } 17 } 18 return -1; 19 } 20 private: 21 vector<int> kmpProcess(string& needle) { 22 int n = needle.length(); 23 vector<int> lps(n, 0); 24 for (int i = 1, len = 0; i < n; ) { 25 if (needle[i] == needle[len]) 26 lps[i++] = ++len; 27 else if (len) len = lps[len - 1]; 28 else lps[i++] = 0; 29 } 30 return lps; 31 } 32 };
