Z-Function. String algorithms. Optimize for large strings

The problem:



Given a string s. For each i from 1 to |s|, find the number of occurrences of its prefix of length i in the string.


Input:

The first line of input contains an integer q (1≤q≤10^5) — the number of datasets in the test.


Each dataset consists of a string s. The length of the string s is from 1 to 10^6 characters. The string consists exclusively of lowercase Latin alphabet letters.


The sum of the lengths of strings s across all q datasets in the test does not exceed 10^6.


Output:

For each dataset, output |s| integers c1, c2, ..., c|s|, where c[i] is the number of occurrences of the prefix of length i in the string s.


Example


Input:
5
abacaba
eeeee
abcdef
ababababa
kekkekkek



Output:
4 2 2 1 1 1 1
5 4 3 2 1
1 1 1 1 1 1
5 4 4 3 3 2 2 1 1
6 3 3 2 2 2 1 1 1



The task must be solved exclusively using the Z-function, and the total time for a string of length 10^6 characters should not exceed 2 seconds.



My solution looks like this:
#include
#include
#include

std::vector ZFunc(const std::string& s) {
const int sz = s.size();
std::vector z(sz, 0);

for (int i = 1, l = 0, r = 0; i != sz; ++i) {
if (r >= i)
z[i] = std::min(z[i - l], r - i + 1);

while (z[i] + i < sz && s[i + z[i]] == s[z[i]])
z[i]++;

if (z[i] > r - i + 1) {
l = i;
r = i + z[i] - 1;
}
}

return z;
}

int main() {
int n;
std::cin >> n;

std::vector res(n);

for (int k = 0; k != n; ++k) {
std::string s;
std::cin >> s;

res[k].resize(s.size(), 1);
std::vector z = ZFunc(s);

for (int i = 1; i != z.size(); ++i) {
while (z[i]--)
res[k][z[i]]++;
}
}

for (const auto& ivec : res) {
for (int i : ivec)
std::cout