wh1te_whale's blog

Getting WA
By wh1te_whale, history, 4 years ago, In English

I am solving some string problems and recently encountered this problem Text Editor.

I am creating a new string and then I am calculating the Z array for that string. I am getting WA, and since it's a GYM problem, I am not able to know whether I am looking in the right direction.I can not find any Editorial for the same. Can you provide some idea to solve it? The link to my Solution.

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Well, my only idea is to use binary search+KMP(Rolling hash). Binary search for the longest string starting from prefix(this is for the second string) to cut of complexity to O(n^2*log(n)) instead of O(n^3). Then use KMP to optimize pattern finding from O(n) to O(1). So the total complexity becomes O(n*log(n)).

→ Reply