OverKiller's blog

By OverKiller, history, 4 years ago, In English

This problem appeared in a Hiring Challenge on Hackerrank and i couldn't solve it in better than $$$O(N^2)$$$ which was giving TLE. Here is the problem below:

Spoiler

I can't think of a solution better than $$$O(N^2)$$$. Any help/hints will be appreciated.

Full text and comments »

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

By OverKiller, history, 4 years ago, In English

Recently, i was learning kmp(from cp-algorithms) and in it's application last part was Building an automaton according to the prefix function link to article.
I am having hard time understanding what aut[i][c] stores here and how can we use it to find longest suffix which is also a prefix of text by adding character c at position i. I tried printing the values stored in aut[i][c] and the corresponding substring but couldn't understand what do they store?
Any help or example to demonstrate this would be much appreciated.
Thanks in advance.

Full text and comments »

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