You are not logged in. Please login at www.codechef.com to post your questions!

×

TASHIFT - Editorial

12
3

Problem link : contest practice

Difficulty : Simple

Pre-requisites : Strings, KMP

Problem : Given two String A and B of the same length. You can do some (may be none) shift operations which results in the first character of B moving to the end. What is the minimum number of operations that are needed so that B has the longest common prefix with A.

Explanation

At first, let's consider some partial solutions.

How to get 30 points

Just try implement the shift operations in O(N) and try all possible numbers of Shift operations on B. You properly even do not need write so much code if your language have some built-in library for string. You also do not have to do anything to speed up the string comparison. The overall complexity is O(N2).

How to get 60 points

Let's say we append string B at the end of string B. We get: B1,B2...BNB1,B2...BN. The thing worth noting is that after K shift operations we get BK+1,BK+2...BN,B1,B2...BK. This string(which we get after K shift operations) is now a substring of the new string that we got by appending B at the end of B.
So we'll now search all prefixes of A in B.B(means concatanation of B with B) which will help us in knowing which prefixes of A are present in B.B. Let's say we have to search a string A of length M in a string B of length N. What we can do is generate hash of all substrings of B which are of length M and search for hash of string A in the generated hashes.
A hash function of string S could be say Summation[i=0 to length][26i*(S[i]-'a')] modulo some prime P. If we have the hash of a substring of length N say S[i,i+N], we can easily generate hash of S[i+1,i+N+1] by using inverse modulo since we are using a prime for modulo operations.

How to get 100 points

You need to know string matching algorithm KMP to get full points. You can learn KMP here, here, or anywhere you like to :).
KMP helps us in finding all prefixes of a string X in string Y. So we'll search A in B.B(means concatanation of B with B) which will help us in knowing which prefixes of A are present in B.B. We'll choose an answer that gives us the largest prefix, also it'll give the index at which that prefix matches, from which we can find the number of shifts required.

Solutions : setter tester

This question is marked "community wiki".

asked 27 Jul '14, 14:47

darkshadows's gravatar image

5★darkshadows ♦
3.0k93163187
accept rate: 12%

edited 30 Jul '14, 18:25

admin's gravatar image

0★admin ♦♦
19.5k348496535

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

(30 Jul '14, 19:05) ritesh_malav4★

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

(14 Jun '17, 00:58) anujagrawal13★

12next »

You can also use Z-algorithm. Here is how.

link

answered 27 Jul '14, 15:00

Debanjan's gravatar image

2★Debanjan
34659
accept rate: 12%

Even the test cases of this problem are weak ... check out my submission ,it passes without appending string B... (i.e; it passes directly by finding prefix of A in B)

solution link : http://www.codechef.com/viewsolution/4396688

link

answered 28 Jul '14, 15:09

grayhathacker's gravatar image

5★grayhathacker
3374514
accept rate: 0%

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

My Solution: here

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!!!

link

answered 30 Jul '14, 14:31

upendra1234's gravatar image

2★upendra1234
2.3k183069
accept rate: 1%

edited 30 Jul '14, 14:31

Why do we need to append B to itself ?

(20 Mar '16, 18:37) shubham992★

Why do we need to append B to itself?

(14 Jun '17, 01:08) anujagrawal13★

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

(20 Jun '17, 00:49) shubham_23244★

WHAT is the correct output FOR this input? 4 ccad ccca

The ac solutions are giving different output. my solution ig giving the output 1

link

answered 27 Jul '14, 16:23

khatribru's gravatar image

6★khatribru
142
accept rate: 0%

Mine is giving 1, which is correct.

(27 Jul '14, 17:05) alexvaleanu4★

Can any one please say why my code fails(I know my code gives TLE but it shows WA)
http://www.codechef.com/viewsolution/4391697

link

answered 27 Jul '14, 15:21

achaitanyasai's gravatar image

5★achaitanyasai
2.2k61747
accept rate: 10%

http://www.codechef.com/viewsolution/4391999

My solution gives TLE in one-task of subtask 2 and 3. Can someone check it and tell why it is so...

link

answered 27 Jul '14, 16:13

vipsharmavip's gravatar image

6★vipsharmavip
3227
accept rate: 23%

can somebody please tell me on which test case is it failing? My code : http://ideone.com/HKkgUZ It is failing on the last testcase of subclass1.

link

answered 27 Jul '14, 16:19

harshit1205's gravatar image

3★harshit1205
1804613
accept rate: 0%

try test case: 4 cccc cccc

output is 0

(28 Jul '14, 09:02) utkarsh134★

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: http://www.codechef.com/viewsolution/4405550

(30 Jul '14, 18:21) harshit12053★

O(N^2) with minor optimisations was also accepted: http://www.codechef.com/viewsolution/4384460

link

answered 27 Jul '14, 17:05

alexvaleanu's gravatar image

4★alexvaleanu
5591312
accept rate: 7%

One can also solve this problem with hashes in O(N*logN).

link

answered 27 Jul '14, 17:33

lebron's gravatar image

7★lebron
3.2k317
accept rate: 25%

How exactly?

(27 Jul '14, 18:21) wittyceaser2★

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.

(28 Jul '14, 11:02) alexvaleanu4★

Can someone check my solution, i used a simple suffix array (created by using manber's)for the question and i was very much sure that the approach can do this task in O(n * log^2(n)) but it resulted in TLE even when n is 10^4. Here is the code of my solution. http://www.codechef.com/viewsolution/4391961

link

answered 27 Jul '14, 20:12

dragonslayerx's gravatar image

5★dragonslayerx
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,481
×348
×66
×12

question asked: 27 Jul '14, 14:47

question was seen: 9,430 times

last updated: 21 Aug, 01:01