TASHIFT : Editorial

editorial
,
1

Link to the Contest:
https://www.codechef.com/CSPK2020

TASHIFT : Editorial
Author: tuananh93
Tester: easy3279
Editorialist : chaitanya_44
Difficulty : Easy
Problem:

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
The first line of the input contains a single integer N. The second and the third lind contains the string A and B respectively.

Constraints
30 points:

1 ≤ N ≤ 5000
30 points:

1 ≤ N ≤ 104
40 points:

1 ≤ N ≤ 106

Solution:

cpp 14:

#pragma GCC optimize(“Ofast”)
#include<bits/stdc++.h>
#include
using namespace std;

#define mod 1000000007
#define one(x) __builtin_popcountll(x)
#define pp pair<ll,ll>
#define all(x) (x).begin(), (x).end()
#define removeDuplicates(a) a.resize(unique(all(a))-a.begin())
typedef long long int ll;

const int mxn = 2e5+10;
const int MAX_CHAR = 26;
ll a[mxn];
ll b[mxn];

void subMain(){
int n;
string a,b;
cin>>n>>a>>b;
b+=b;
int m=0, i=0, j=0, shift=0;

for(int x=0;x<n;x+=i){
    i=0;j=0;
    for(int ii=x;ii<n;ii++){
        if(b[ii]!=a[0]){
            x++;
        }else{
            break;
        }
    }
    for(int ii=x;ii<2*n;ii++){
        if(b[ii]==a[j++]){
            i++;
        }else{
            break;
        }
    }
    if(m<i){
        m=i;
        shift=x;
    }
}
cout<<shift<<endl;

}

int32_t main(){

ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);


/*ll t;
cin >> t;
while(t--){
    subMain();
}*/
subMain();
cerr<<"Time : "<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
return 0;

}

PYTHON3.6:

cook your dish here

n = int(input())
a = input()
b = input()
lo,hi=0,n-1
res = ‘#’
while(lo <= hi):
mid = (lo + hi)//2
if(a[:mid+1] in b):
res=a[:mid+1]
lo=mid+1
else:
hi=mid-1
ans=b.index(res)
print(ans)