Ahmed_Araby's blog

issue in Z- Algorithm implementation

By Ahmed_Araby, history, 6 years ago, In English

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

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

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 ?

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

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply