priojeet_priyom's blog

how to solve 149 E (getting TLE)
By priojeet_priyom, history, 6 years ago, In English

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

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

»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Recently learned z-algo. that is why I was trying to solve it wtih z-algo.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

https://codeforces.net/contest/149/submission/41916084

You 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.

→ Reply