Hello coders, today we are going to solve Shift The String CodeChef Solution whose Problem Code is TASHIFT.
Task
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
ccadd
bddccSample Output
3Solution – 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.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
class Test
{
public static void main(String[]args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int num=Integer.parseInt(br.readLine());
String a=br.readLine();
String b=br.readLine();
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.