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
pi->z
You can try to google translate this adamant's blog
thanks, ill look into it!
I found this simple conversion too
Edited: Sorry :( It should have an extra loop too
wow.. that was really nice
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.
:(
The correct version seems to have an extra for-loop
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.
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.
s[0:p[i]] == s[i-p[i]+1:i]
(i-p[i]+1)
is a prefix ofs
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.
XD
A blue guy once invented Splay Trees, though.
Source?
https://codeforces.net/profile/Darooha
How? Feeling proud I was blue(still performing in blue level though)
Wait, but what is Z-function?
What is new? Blues know more algorithms than reds since the dawn of time.
But, weren't all red once blue? :o
blue is a genius color when you pass the blue you lost your geniusity
I would get my geniousity back in next round.
me2 XD
.