| 19 | string pat; |
| 20 | public: |
| 21 | void init() { |
| 22 | string pat = this->pat; |
| 23 | dfa.clear(); |
| 24 | int shadow_state = 0; |
| 25 | dfa.push_back(vector<int>(256, 0)); |
| 26 | dfa[0][pat.at(0)] = 1; |
| 27 | for (int i = 1; i < pat.size(); i ++ ) { |
| 28 | dfa.push_back(dfa[shadow_state]); |
| 29 | dfa[i][pat.at(i)] = i + 1; |
| 30 | shadow_state = dfa[shadow_state][pat.at(i)]; |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | int strStr(string haystack, string needle) { |
| 35 | if (needle.empty()) return 0; |