Blog entries - Codeforces

#	User	Rating
1	tourist	3565
2	Benq	3540
3	Petr	3519
4	maroonrk	3503
5	jiangly	3391
6	ecnerwala	3363
7	Radewoosh	3349
8	scott_wu	3313
9	ainta	3298
10	boboniu	3289

#	User	Contrib.
1	1-gon	200
2	Errichto	196
3	rng_58	194
4	SecondThread	186
5	awoo	185
6	Um_nik	182
7	vovuh	179
8	Ashishgup	176
9	maroonrk	174
10	-is-this-fft-	173

I was solving the string section problems from Brazilian summer camp 2018, and there were following problems:

You are given z-function of some (unknown for you) string s, write prefix-function of the string s.

You are given prefix-function of some (unknown for you) string s, write z-function of the string s.

I thought that if these were solvable, just storing all the equality information would suffice on both problems, and they indeed got AC (Code below). But I have no clue how to prove either of these, and I couldn't find the editorial on google.

Can someone tell me how to prove these?

z->pi

struct disjoint_set{
	vector<int> p;
	disjoint_set(int n): p(n, -1){ }
	bool share(int a, int b){ return root(a) == root(b); }
	int sz(int u){ return -p[root(u)]; }
	int root(int u){ return p[u] < 0 ? u : p[u] = root(p[u]); } // O(alpha(n))
	bool merge(int u, int v){
		u = root(u), v = root(v);
		if(u == v) return false;
		if(p[u] > p[v]) swap(u, v);
		p[u] += p[v], p[v] = u;
		return true;
	}
};
 
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n;
	cin >> n;
	vector<int> z(n);
	for(auto i = 0; i < n; ++ i) cin >> z[i];
	disjoint_set dsu(n);
	for(auto i = 1, j = 0; i < n; ++ i){
		int zi = 0;
		if(i < j + z[j]) zi = min(j + z[j] - i, z[i - j]);
		while(zi < z[i]) dsu.merge(zi, i + zi), ++ zi;
		if(i + z[i] > j + z[j]) j = i;
	}
	vector<int> pi(n);
	for(auto i = 1; i < n; ++ i){
		int len = pi[i - 1];
		while(len && !dsu.share(i, len)) len = pi[len - 1];
		if(dsu.share(i, len)) pi[i] = len + 1;
	}
	for(auto x: pi) cout << x << " ";
	cout << "\n";
	return 0;
}

pi->z

struct disjoint_set{
	vector<int> p;
	disjoint_set(int n): p(n, -1){ }
	bool share(int a, int b){ return root(a) == root(b); }
	int sz(int u){ return -p[root(u)]; }
	int root(int u){ return p[u] < 0 ? u : p[u] = root(p[u]); } // O(alpha(n))
	bool merge(int u, int v){
		u = root(u), v = root(v);
		if(u == v) return false;
		if(p[u] > p[v]) swap(u, v);
		p[u] += p[v], p[v] = u;
		return true;
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n;
	cin >> n;
	vector<int> pi(n);
	for(auto i = 0; i < n; ++ i) cin >> pi[i];
	disjoint_set dsu(n);
	for(auto i = 1; i < n; ++ i) if(pi[i]) dsu.merge(i, pi[i] - 1);
	vector<int> z(n);
	for(auto i = 1, j = 0; i < n; ++ i){
		if(i < j + z[j]) z[i] = min(j + z[j] - i, z[i - j]);
		while(i + z[i] < n && dsu.share(z[i], i + z[i])) ++ z[i];
		if(i + z[i] > j + z[j]) j = i;
	}
	for(auto x: z) cout << x << " ";
	cout << "\n";
	return 0;
}

DreamingLeaf's blog