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

Автор Ahmed_Araby, история, 5 лет назад, По-английски

I just learned Z-algorithm (string processing) and in every problem I solve on it when I start the main outer loop of the function from the index 0 I get TLE but when I start from 1 I get Accepted

for example problem 127D - Password

(here I use the algorithm for matching the string with it self to find out max length of sub string that start at any index i and match a prefix of the whole string)

this submission start the loop from 0 and get TLE 54993356 but this submission start from 1 and get Accepted 54993706

and this is the only change that I made for the Accepted solution ( for(int i=1; i<n; i++) // i start form 1 instead of 0 ************************** ) you can see this in the second submission

so some one could give me a reason and tell my why this happen ? thanks in advance

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

just copy the algorithm from emaxx and get AC. Life is too short to waste time on implementation details. Better use that time to solve more problems :)

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Try tracing the algo by hand. If you have difficulty, use a debugger to step through.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I used an implementation from cp-algorithm site and changed the initial value of first loop counter to 0 and condition of editing the most right boundary "r" to <= and I GET TLE also and in the case of a string of length 1e6 the number of operation in both implementation implementation with loop starting from 1 ->> 999999 opearion implementation with loop starting from 0 ->> 1999999 opearion

so 2nd implementation is just twice as 1st implementation and this is just because an n operation that happen at the first time when we start from 0

and I did tracing for the implementation that get TLE it by hand it just and found no thing that could be the reason for the TLE

so what I'm missing here ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You miss that after processing 0 you get l=0, r=n-1 and that's why your solution works in $$$O(n^2)$$$ because for each $$$i$$$ it does $$$z[i] = min(n-1-i+1, z[i-0]) = z[i] = 0$$$ so your code works as a naive approach.

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I think the test is like jjjj...jaa, and the variable $$$l$$$ will always be 0, so your approach will execute $$$O(n^2)$$$ operations.