leetcode

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 };