| 249 | // Algorithms on Strings, Trees, and Sequences: Computer Science and |
| 250 | // Computational Biology |
| 251 | template <class T> std::vector<int> z_algorithm(const std::vector<T>& s) { |
| 252 | int n = int(s.size()); |
| 253 | if (n == 0) return {}; |
| 254 | std::vector<int> z(n); |
| 255 | z[0] = 0; |
| 256 | for (int i = 1, j = 0; i < n; i++) { |
| 257 | int& k = z[i]; |
| 258 | k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]); |
| 259 | while (i + k < n && s[k] == s[i + k]) k++; |
| 260 | if (j + z[j] < i + z[i]) j = i; |
| 261 | } |
| 262 | z[0] = n; |
| 263 | return z; |
| 264 | } |
| 265 | |
| 266 | std::vector<int> z_algorithm(const std::string& s) { |
| 267 | int n = int(s.size()); |