# Shift The String | CodeChef Solution

Hello coders, today we are going to solve Shift The String CodeChef Solution whose Problem Code is TASHIFT.

You are given two stringsÂ AÂ andÂ BÂ of the same length. Each string containsÂ NÂ Lower case Latin character (from ‘a’ to ‘z’). A shift operation will remove the first character of a string and add the same character at the end of that string. For example after you perform a shift operation on a string ‘abcd’, the new string will be ‘bcda’. If you perform this operation two times, the new string will be ‘cdab’. You need to use some (maybe none) shift operations on the stringÂ BÂ to maximize the length of the longest common prefix ofÂ AÂ andÂ B. If more than one result can be found pick the one that use smallest number of shift operations.

## Input Format

The first line of the input contains a single integerÂ N. The second and the third lind contains the stringÂ AÂ andÂ BÂ respectively.

## Output Format

Contains a single integer which is the number of shift operations.

## Constraints

30 points:

• 1 â‰¤ N â‰¤ 5000

30 points:

• 1 â‰¤ N â‰¤ 104

40 points:

• 1Â â‰¤Â NÂ â‰¤Â 106

Example

Sample Input

``````5
bddcc``````

Sample Output

``3``

## Solution – Shift The String

C++

```#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

#define len(s) s.size()

#define vll vector<ll>
#define pb(x) push_back(x)

#define loop(i, st, end, inc) for (int i = st; i < end; i += inc)
#define rloop(i, st, end, dec) for (int i = st; i >= end; i -= dec)

#define cy cout << "YES" << endl
#define cn cout << "NO" << endl

const ll lenOfPrime = 1000;

bool isNotPrime[lenOfPrime];
vector<ll> primes;

void seive()
{
isNotPrime[1] = true;
for (int i = 2; i < lenOfPrime; i++)
{
if (!isNotPrime[i])
{
loop(j, i * i, lenOfPrime, i)
{
isNotPrime[j] = true;
}
}
}
loop(i, 2, lenOfPrime, 1)
{
if (!isNotPrime[i])
{
//cout << i << " ";
primes.pb(i);
}
}
}
set<ll> factors;
map<ll, ll> mp;

void primeFacct(ll n)
{

if (n % 2 == 0)
{
factors.insert(2);
}
while (n % 2 == 0)
{
n /= 2;
mp[2]++;
//cout << 2 << " ";
}
loop(i, 3, sqrt(n) + 1, 2)
{
if (n % i == 0)
{
factors.insert(i);
}
while (n % i == 0)
{
//cout << i << " ";
mp[i]++;
n /= i;
}
}
if (n > 2)
{
//cout << n << endl;
mp[n]++;
factors.insert(n);
}
}

ll numOfFactor(ll n)
{
ll cnt = 1;
loop(i, 0, len(primes), 1)
{
if (primes[i] * primes[i] * primes[i] > n)
{
break;
}
else
{
ll c = 1;
while (n % primes[i] == 0)
{
n /= primes[i];
c++;
}
cnt = cnt * c;
}
}
ll root = sqrt(n);
if (!isNotPrime[n])
{
cnt *= 2;
}
else if (!isNotPrime[root] && (root * root == n))
{
cnt *= 3;
}
else
{
if (n != 1)
{
cnt *= 4;
}
}
return cnt;
}

///for specific problem

void solve()
{
ll n;
cin >> n;
string s1, s2;
cin >> s1 >> s2;
s1 += "1";
s2 += "2";
ll i = 0, hm = 0, ans = 0;

//cout << len(s1) << endl;
//cout << s1 << " " << s2 << endl;

vector<pair<ll, ll>> vec;

loop(j, 0, n + 1, 1)
{
if (s1[i] != s2[j])
{
//cout << s1[i] << " " << s2[j] << " " << i << " " << j << endl;
if (i > hm)
{
hm = i;
ans = j - i;
}

i = 0;
if (s1[i] == s2[j])
{
i++;
}
}
else
{
i++;
}
}

for (auto i : vec)
{
//cout << i.first << " " << i.second << endl;
}

//cout << hm << endl;
cout << ans << endl;
}
int main()
{
solve();
}
/*

9
aaabcccaa
abaaaccaa

*/```

Python

```def LPS(s):
lps = [0 for i in range(len(s))]
for i in range(1, len(s)):
j = i-1
while (j >= 0) and (s[lps[j]] != s[i]):
j = lps[j]-1

if (j >= 0):
lps[i] = lps[j]+1

return lps

N = int(input())
A = input()
B = input()

lpsA = LPS(A)
a = 0
b = 0
shifts = 0
curShift = 0
longPref = 0
while (curShift < N):
while (a < len(A)) and (b < len(B)) and (A[a] == B[b]):
a += 1
b += 1

assert ((a < len(A)) and (b < len(B))) or ((a == len(A)) and (b == len(B)))
if (a > longPref):
shifts = curShift
longPref = a

if (a == 0):
B += B[b]
curShift += 1
b += 1
elif (a == len(A)):
break
else:
B += B[b-a:b-lpsA[a-1]]
curShift += a-lpsA[a-1]
a = lpsA[a-1]

print(shifts)```

Java

```import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;

class Test
{
public static void main(String[]args)throws IOException{
int[]arr=new int[num];
int k=0;
arr[0]=0;
for(int i=1;i<arr.length;i++){
if(a.charAt(i)==a.charAt(k))
arr[i]=++k;
else
k=0;
}
int i=0;
int j=0;
int max=0;
int index=0;
int temp=0;
while(i<a.length()&&temp<(2*num)-1){
char aa=a.charAt(i);
char bb=b.charAt(j);
if(aa==bb){
i++;
if(i>max){
max=i;
index=temp;
}
j=(j+1)%num;
}
else{
if(i==0)
j=(j+1)%num;
else
temp--;
i=arr[i];
}
temp++;
}
if(i==a.length()){
System.out.println((j+num)-max);
}
else if(max==0)
System.out.println(0);
else
System.out.println((index+1)-max);
}
}

/*
8
abcbcabc
abcabcbc

7
abcbcab
cacabcb*/```

Disclaimer: The above Problem (Shift The String) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.