### priojeet_priyom's blog

By priojeet_priyom, history, 7 months 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  Comments (4)
 » 7 months ago, # | ← Rev. 2 →   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
•  » » Recently learned z-algo. that is why I was trying to solve it wtih z-algo.
 » 7 months ago, # | ← Rev. 2 →   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.
•  » » thank you :)