Stream_Cipher's blog

By Stream_Cipher, history, 6 weeks ago, In English

I write a nlogn solution for this problem but it is giving tle how to solve this using KMP or other string matching algorithm. Help will be really appreciated . Thanks :)

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

the problem can solved in O(n) time using the z-function

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use string hashing.

my submission

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use lps(prefix function array) array .there you can start from last index(i=n-1) add its lps value to answer and move i to index lsp[i]-1 till i>0...

for reference my AC code link..