| 1 | int* compute_pi(const string &t) { |
| 2 | int m = t.size(); |
| 3 | int *pit = new int[m + 1]; |
| 4 | if (0 <= m) pit[0] = 0; |
| 5 | if (1 <= m) pit[1] = 0; |
| 6 | rep(i,2,m+1) { |
| 7 | for (int j = pit[i - 1]; ; j = pit[j]) { |
| 8 | if (t[j] == t[i - 1]) { pit[i] = j + 1; break; } |
| 9 | if (j == 0) { pit[i] = 0; break; } } } |
| 10 | return pit; } |
| 11 | int string_match(const string &s, const string &t) { |
| 12 | int n = s.size(), m = t.size(); |
| 13 | int *pit = compute_pi(t); |