#include<bits/stdc++.h> #define ll long long // Return an array result // result[i] is the maximum number x that base[i:i+x] equals to pattern[:x] int* Zalgo(string base, int base_size, string pattern, int pattern_size) { string s = pattern + base; int n = pattern_size + base_size; int z[n]; int L = 0, R = 0; for (int i = 1; i < n; i++) { if (i > R) { L = R = i; while (R < n && s[R - L] == s[R]) R++; z[i] = R - L; R--; } else { int k = i - L; if (z[k] < R - i + 1) z[i] = z[k]; else { L = i; while (R < n && s[R - L] == s[R]) R++; z[i] = R - L; R--; } } } int *result = new int[base_size]; for (int i = pattern_size; i < n; ++i) { result[i - pattern_size] = min(z[i], pattern_size); } return result; }