TASHIFT - Editorial

general
, , ,
11

Really Nice question. Using KMP algorithm you can easily solve it.

My Solution: [here][1]

Algorithm:

  1. B = B + B; // append string B to B itself.

  2. Generate lps[] array for string A.

  3. Now the main algorithm. start traversing the second string and keep track of the maximum prefix found.

    int res = 0, best = 0, ans = 0;
    int j = 0;
    i = 0;
    while(i < n) {
    if(A[j] == B[i]) {
    j++;
    i++;
    best++;
    }
    if(best > res) {
    res = best;
    ans = i-j;
    }
    if(j == m) {
    break;
    }
    if(A[j] != B[i]) {
    best = 0;
    if(j != 0) {
    j = lps[j-1];
    }else {
    i++;
    }
    }
    }
    printf(“%d\n”, ans);

Ask me if anything is not clear.

Happy Coding!!!
[1]: CodeChef: Practical coding for everyone

2 Likes
12

why we need to concatenate b?

13

on submitting my code the judge responses as run time error in all test-cases , can anybody help me out here…?

14

refer to this


[1] for above mentioned problem.


  [1]: https://www.codechef.com/viewsolution/13622248
15

Please help me with my code , I have used KMP algorithm and I am getting a wrong answer.
Which might be the test cases getting wrong ??
https://www.codechef.com/viewsolution/14293528

16

could someone give me a counterexample for my code. i’m getting WA but cannot find a simple counterexample.
code: https://www.codechef.com/viewsolution/19812182

17

Mine is giving 1, which is correct.

18

How exactly?

19

try test case:
4
cccc
cccc

output is 0

20

One way I thought of in the contest was this: First you double B. For both A and B you store hashes in order to be easy to find the hash value of a substring( eg hash(A[2…5]) ). After that, for every suffix of B you search( using binary search) the longest common prefix with A. You will need hashes to compare in O(1) strings.

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.