leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0028.cpp (668B)

      1 class Solution {
      2   public:
      3     int strStr(string haystack, string needle) {
      4         vector<int> table(needle.size(), 0);
      5 
      6         int m = haystack.size(), n = needle.size();
      7         for (int len = 0, j = 1; j < n;) {
      8             if (needle[j] == needle[len])
      9                 table[j++] = ++len;
     10             else if (len)
     11                 len = table[len - 1];
     12             else
     13                 table[j++] = 0;
     14         }
     15 
     16         for (int i = 0, j = 0; i < m;) {
     17             if (haystack[i] == needle[j]) i++, j++;
     18             if (j == n) return i - j;
     19             if (i < m && haystack[i] != needle[j]) j ? j = table[j - 1] : i++;
     20         }
     21 
     22         return -1;
     23     }
     24 };