CSES - Aalto Competitive Programming 2024 - wk9 - Homework - Results
Submission details
Task:Z-array
Sender:snude
Submission time:2024-11-02 13:00:37 +0200
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6--details
#7--details
#8ACCEPTED0.09 sdetails
#9ACCEPTED0.08 sdetails
#10--details
#11ACCEPTED0.01 sdetails
#12--details
#13--details

Compiler report

input/code.cpp: In function 'int main(int, char**)':
input/code.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%s", n);
      |         ~~~~~^~~~~~~~~

Code

#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(char s[], vector<int> &z, int n)
{
	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
	char n[1000000];
	// cin >> n;
	scanf("%s", n);

	vector<int> z(1000000);
	int len = strlen(n);
	create_z_array(n, z, len);
	// for (unsigned int i = 0; i < n.size(); i++) {
	// 	cout << z[i] << " ";
	// }
	// char s = n[0];
	// int i = 0;
	z[0] = len;
	for (int i = 0; i < len; i++) {
		cout << z[i] << " ";
	}
	// while (s != '\0') {
	// 	cout << z[i] << " ";
	// 	i++;
	// 	s = n[i];
	// }
	cout << "\n";

	return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
aaaaaaaaaa

correct output
10 9 8 7 6 5 4 3 2 1 

user output
10 9 8 7 6 5 4 3 2 1 

Test 2

Verdict: ACCEPTED

input
ababababab

correct output
10 0 8 0 6 0 4 0 2 0 

user output
10 0 8 0 6 0 4 0 2 0 

Test 3

Verdict: ACCEPTED

input
aabababaaa

correct output
10 1 0 1 0 1 0 2 2 1 

user output
10 1 0 1 0 1 0 2 2 1 

Test 4

Verdict: ACCEPTED

input
ahtqqkhrrn

correct output
10 0 0 0 0 0 0 0 0 0 

user output
10 0 0 0 0 0 0 0 0 0 

Test 5

Verdict: ACCEPTED

input
mqdozmqdoz

correct output
10 0 0 0 0 5 0 0 0 0 

user output
10 0 0 0 0 5 0 0 0 0 

Test 6

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
1000000 999999 999998 999997 9...

user output
(empty)

Test 7

Verdict:

input
ababababababababababababababab...

correct output
1000000 0 999998 0 999996 0 99...

user output
(empty)

Test 8

Verdict: ACCEPTED

input
baaaabbabaabbbbaaaabbbababaaba...

correct output
1000000 0 0 0 0 1 2 0 3 0 0 1 ...

user output
1000000 0 0 0 0 1 2 0 3 0 0 1 ...
Truncated

Test 9

Verdict: ACCEPTED

input
ltpbdybvcpychbsplyonjfmdtsnqwt...

correct output
1000000 0 0 0 0 0 0 0 0 0 0 0 ...

user output
1000000 0 0 0 0 0 0 0 0 0 0 0 ...
Truncated

Test 10

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
1000000 99998 99997 99996 9999...

user output
(empty)

Test 11

Verdict: ACCEPTED

input
abaababaab

correct output
10 0 1 3 0 5 0 1 2 0 

user output
10 0 1 3 0 5 0 1 2 0 

Test 12

Verdict:

input
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

correct output
1000000 499999 499998 499997 4...

user output
(empty)

Test 13

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
1000000 147418 147417 147416 1...

user output
(empty)