TASHIFT - Editorial

general
, , ,
21

Thanks a lot! That was a problem, but it still gives WA on the last one of subclass1. What can be the problem? Here’s my code: CodeChef: Practical coding for everyone

22

thank a lot learned the algorithm (KMP) and nice technique

23

Why do we need to append B to itself ?

24

Why are we concatenating B with B before applying the KMP algorithm?

25

Why do we need to append B to itself?

26

@upendra1234,
Take a test case :
9
abcabdfeg
abcabcabd.
Your accepted code is giving answer 0 , but the correct answer is 3 .

1 Like
27

There is no need to concatenate it

28

because there can be possibly n-1 shifts where n is the length of string.
example : aba
its possible shifts are : 1. aba ( not shifting )
2. baa
3. aab
in the example if we perform one more shift it will become aba.
now if we concatenate like mentioned in the editorial
abaaba
we can get all the possible shifts in the single string.
like mentioned in the example abaaba will contain

  1. aba
  2. baa
  3. aab
29

Ah this can be done using KMP using just two simple loops…
note: people make errors while taking the indices incorrecly

30

Even I had the the similar error. It was because of use of uninitialized values. In your case it might be
because of the case when variable r is uninitialized(length of longest common prefix for all shifts being 0) and the program selects one default value. Mine got accepted when i corrected this.

31

@legion12 Bhai Madad karna Achchha h par check toh kar leta ki voh comment 2014 ka h :sweat_smile:

32

awesome this is why ypu are 6 star coder