[LeetCode] Implement strStr()-白红宇

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.

;

, 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
     
       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
      
        kmpProcess(string& needle) {22         int n = needle.length();23         vector
       
         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 };