| 67 | } |
| 68 | |
| 69 | int strStr(string haystack, string needle) { |
| 70 | if (needle.empty()) return 0; |
| 71 | if (haystack.empty()) return -1; |
| 72 | auto next = getNext(needle); |
| 73 | // for (auto i : next) cout << i << ' '; |
| 74 | // cout << endl; |
| 75 | int i = 0, j = 0; |
| 76 | while ( i < haystack.size() and j < (int) needle.size() ) { |
| 77 | // cout << i << ' ' << j << endl; |
| 78 | if (j == -1 or haystack[i] == needle[j]) { |
| 79 | i ++ ; |
| 80 | j ++ ; |
| 81 | } else { |
| 82 | j = next[j]; |
| 83 | } |
| 84 | // cout << i << ' ' << j << endl; |
| 85 | // cout << haystack.size() << needle.size(); |
| 86 | // cout << (j < needle.size()); |
| 87 | } |
| 88 | // cout << j; |
| 89 | if (j == needle.size()) return i - j; |
| 90 | else return -1; |
| 91 | } |
| 92 | }; |
| 93 | |
| 94 | int main() { |