leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0028.cpp (668B)

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