计算kmp前缀表，用于匹配失败后进行回退操作
| 10 | |
| 11 | // 计算kmp前缀表，用于匹配失败后进行回退操作 |
| 12 | std::vector<int> compute_prefix_function(std::string& p) |
| 13 | { |
| 14 | int n = p.length(); |
| 15 | std::vector<int> prefix(n); |
| 16 | |
| 17 | prefix[0] = -1; |
| 18 | int j = 0; |
| 19 | int k = -1; |
| 20 | |
| 21 | while (j < n - 1) { |
| 22 | if (k == -1 || p[k] == p[j]) { |
| 23 | // 如果相同，则记录当前k的位置 |
| 24 | k++; |
| 25 | j++; |
| 26 | prefix[j] = k; |
| 27 | } else { |
| 28 | // 不同则回退 |
| 29 | k = prefix[k]; |
| 30 | } |
| 31 | } |
| 32 | |
| 33 | return prefix; |
| 34 | } |
| 35 | |
| 36 | int kmp_matcher(std::string& t, std::string& p) |
| 37 | { |