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.
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)).
Thanks!