Problem converting Z function to prefix function and vice versa

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
7	SecondThread	150
9	orz	146
10	pajenegod	145

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

3 years ago, # |

+44

You can try to google translate this adamant's blog

→ Reply

Savior-of-Cross

3 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

23 months 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.