Z-array

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#define debug_print(fmt, args...) printf(fmt, ##args)
#else
#define deb(fmt, args...)
#define debug_print(fmt, args...)
#endif

void print_array(vector<int> in, const string title = "Vector")
{
	debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
	for (unsigned int i = 0; i < in.size(); i++) {
		debug_print("%d ", in[i]);
	}
	debug_print("\nDEBUG: ] END\n");
}

void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
	debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
	for (unsigned int i = 0; i < in.size(); i++) {
		for (unsigned int j = 0; j < in[i].size(); j++) {
			debug_print("%d ", in[i][j]);
		}
		debug_print("\nDEBUG: ");
	}
	debug_print("DEBUG: ] END\n");
}

/**
 * This algorithm is heavily inspired by the algorithm presented in the textbook.
 * Not very easy to not copy it fully, if one tries to implement the algorithm
 * as described in the textbook.
 *
 * If this is too much of "copying" the algorithm then give be a fail.
 */
void create_z_array(string s, vector<int> &z)
{
	int n = s.size();
	int r = 0, l = 0;
	cout << n << " ";
	for (int i = 1; i < n; i++) {
		// z[i] = max(0, min(z[i - l], r - i + 1));
		// deb("e: i: %d l: %d, r: %d, z[i]: %d\n", i, l, r, z[i]);
		if (i + z[i - l] < r) {
			// z[i] = z[i - l];
			z[i] = max(0, min(z[i - l], r - i + 1));
		} else {
			// z[i] = z[i - l];
			l = i;
			z[i] = max(0, min(z[i - l], r - i + 1));
			// deb("z[i - l]: %d, r - i + 1: %d\n", z[i - l], r - i + 1);
			while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
				// deb("while\n");
				r = i + z[i]; // have to this instead of r++ as r is one behind of z[i]
				z[i]++;
			}
		}
		cout << z[i] << " ";
		// deb("j: i: %d l: %d, r: %d, z[i]: %d\n", i, l, r, z[i]);
	}
	z[0] = n;
}

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	// Read the input parameters
	string n;
	cin >> n;

	vector<int> z(n.size());
	create_z_array(n, z);
	// for (unsigned int i = 0; i < n.size(); i++) {
	// 	cout << z[i] << " ";
	// }
	cout << "\n";

	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED