| 32 | } |
| 33 | |
| 34 | int strStr(string haystack, string needle) { |
| 35 | if (needle.empty()) return 0; |
| 36 | if (haystack.empty()) return -1; |
| 37 | this->pat = needle; |
| 38 | this->init(); |
| 39 | string txt = haystack; |
| 40 | int state = 0, found = needle.size(); |
| 41 | for (int i = 0; i < txt.size(); i ++ ) { |
| 42 | state = this->dfa[state][haystack.at(i)]; |
| 43 | if (state == found) return i - needle.size() + 1; |
| 44 | } |
| 45 | return -1; |
| 46 | } |
| 47 | }; |
| 48 | |
| 49 | // kmp next version |