DreamingLeaf's blog

By DreamingLeaf, 4 months ago, In English

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?


Read more »

  • Vote: I like it
  • +40
  • Vote: I do not like it