Блог пользователя priojeet_priyom

how to solve 149 E (getting TLE)
Автор priojeet_priyom, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, # |
← 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

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

https://mirror.codeforces.com/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.

→ Ответить