how to solve 149 E (getting TLE)

Revision en3, by priojeet_priyom, 2018-08-20 20:59:34

Tried solving 149 E Martian Strings using z-algo. my approach is: compute z value for pattern$text and reverse(pattern)$reverse(text). then find the minimum index for each prefix length match and find the maximum index suffix length match for all length i (0<=i<length(pattern). the complexity of my code is approx O(m*n) which is 10^7. getting TLE. tried optimizing but no luck till now, also tried reading others code but could make sense out of those. my code: submission link

Tags #149 e, #106 (div. 2), #zalgorithm

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English priojeet_priyom 2018-08-20 20:59:34 8 Tiny change: 'compute z index for patte' -> 'compute z value for patte'
en2 English priojeet_priyom 2018-08-20 19:27:49 55 (published)
en1 English priojeet_priyom 2018-08-20 19:25:29 590 Initial revision (saved to drafts)