why we need to concatenate b?
refer to this
[1] for above mentioned problem.
[1]: https://www.codechef.com/viewsolution/13622248Please 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
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
Mine is giving 1, which is correct.
How exactly?
try test case:
4
cccc
cccc
output is 0
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.
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
thank a lot learned the algorithm (KMP) and nice technique
Why do we need to append B to itself ?
Why are we concatenating B with B before applying the KMP algorithm?
Why do we need to append B to itself?
@upendra1234,
Take a test case :
9
abcabdfeg
abcabcabd.
Your accepted code is giving answer 0 , but the correct answer is 3 .
1 Like
There is no need to concatenate it
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
- aba
- baa
- aab
Ah this can be done using KMP using just two simple loops…
note: people make errors while taking the indices incorrecly
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.
