### priojeet_priyom's blog

By priojeet_priyom, history, 4 weeks ago, ,

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

•
• +5
•

 » 4 weeks ago, # | ← Rev. 2 →   0 Are you interested in only the solution with the z-algo? Solution with hashes is not interesting for you?UPD: I read the problem incorrectly, sorry
•  » » 4 weeks ago, # ^ |   0 Recently learned z-algo. that is why I was trying to solve it wtih z-algo.
 » 4 weeks ago, # | ← Rev. 2 →   +3 https://codeforces.com/contest/149/submission/41916084You had two problems in z-function:1) was:  if(i+z[i]-1 > r) { l = i, r = i; } now:  if(i+z[i]-1 > r) { l = i, r = i + z[i] - 1; } It is very important optimization, because you need always use rightmost segment.2) You calculated Z, started from length of pattern, not from 0. So all Z[0... lenp] were 0, so each time when you used z[i] = min(r-i+1, z[ i-l ]); you always got 0.
•  » » 4 weeks ago, # ^ |   0 thank you :)