Z-algorithm
Code
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
vector<i64> z_algorithm(string S) {
vector<i64> A(S.size());
A[0] = S.size();
int i = 1, j = 0;
while (i < S.size()) {
while (i+j < S.size() && S[j] == S[i+j]) ++j;
A[i] = j;
if (j == 0) { ++i; continue;}
int k = 1;
while (i+k < S.size() && k+A[k] < j) A[i+k] = A[k], ++k;
i += k; j -= k;
}
return A;
}