Problem converting Z function to prefix function and vice versa

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

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;
}

int main(){ int n; cin >> n; vector<int> z(n); vector<int> marked; for(int i = 0; i < n; ++i){ int x; cin >> x; if(i == 0) continue; if(x){ z[i - x + 1] = x; marked.push_back(i - x + 1); } } for(int i = 0; i < marked.size(); ++i){ int r = (i + 1 == marked.size()? n : marked[i + 1]); int pos = marked[i]; for(int j = 1; j < z[pos] && pos + j < r; ++j){ int val = min(z[j], z[pos] - j); z[pos + j] = val; } } for(auto x : z) cout << x << " "; cout << endl; }

Comments (23)

Write comment?

mip182

4 years ago, # |

+44

You can try to google translate this adamant's blog

→ Reply

Savior-of-Cross

4 years ago, # ^ |

thanks, ill look into it!

SPyofgame

← Rev. 2 →

I found this simple conversion too

Edited: Sorry :( It should have an extra loop too

vector<int> pi(n + 1, 0);
for (int i = 0; i < n; ++i) maximize(pi[i + z[i] - 1], z[i]);
for (int i = n; i > 0; --i) maximize(pi[i - 1], pi[i] - 1);

wow.. that was really nice

egor_bb

Unfortunately, it does not work. Consider string $$$s = "aaaa"$$$. $$$P(s)=[1,2,3]$$$, $$$Z(s)= [3,2,1]$$$ (3 values because we can skip the very first letter). Following $$$P\rightarrow Z$$$ conversion, during 3 iterations we will set $$$Z_1$$$ to $$$1$$$, $$$2$$$, and $$$3$$$, but won't touch other elements at all.

← Rev. 4 →

The correct version seems to have an extra for-loop

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){
		int z;
		cin >> z;
		if(z){
			pi[i + z - 1] = max(pi[i + z - 1], z);
		}
	}
	for(auto i = n - 2; i >= 0; -- i){
		pi[i] = max(pi[i], pi[i + 1] - 1);
	}
	for(auto x: pi){
		cout << x << " ";
	}
	cout << "\n";
	return 0;
}

I wonder if there's something simple for pi->z as well. I couldn't get the same correction work for it.

You can find a simple version here (the comment is in Russian, but all you need is code).

thanks. I got the general ideas on why those two codes work but I feel like I'm still missing the "key" reason why they form a one-to-one correspondence in the first place.

Like, the characteristic of the equivalence classes of strings with the same prefix function (or equivalently, the same z-function as shown by these two codes). Maybe I should just study some string processing course instead...

String classes are rather simple: take all prefixes of the string, for the prefix of each length, find a set of all its occurrences in the string. If for two strings these sets are equal for all lengths, you cannot distinguish them, and vice versa.

pauloamed

3 years ago, # ^ |

+15

hey, I was trying to understand the algorithm from adamant's blog and I came with this one. It does the same and uses more memory, but I found it better to understand.

by p-func, s[0:p[i]] == s[i-p[i]+1:i]
the substr starting at (i-p[i]+1) is a prefix of s

mark all positions where pref-func indicates a start of a pref-substr. now, the missing values in z are substr of the already marked substrs
try to fill the inside positions using values of the prefix once a new marked substring starts, start this greedy filling again from this new marked string

these may have a intersection, you can compute the same stuff for both marked strings, but the new one will lead to higher values and we need to maximize stuff here, so just look at the new one.