Problem converting Z function to prefix function and vice versa

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

Комментарии (23)

Написать комментарий?

mip182

4 года назад, # |

+44

You can try to google translate this adamant's blog

→ Ответить

Savior-of-Cross

4 года назад, # ^ |

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 года назад, # ^ |

+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.