Header Ad

HackerEarth Rotation problem solution

In this HackerEarth Rotation problem solution You are given two strings S and T of the same length N. Your task is to convert the string S into T by doing some operations. In an operation, you can delete the first character of the string S and append any character at the end of the string. You are required to determine the minimum number of operations to convert S into T.


HackerEarth Rotation problem solution


HackerEarth Rotation problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007ll
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define pb push_back
#define mp make_pair
#define x first
#define y second
ll lps[1000005], match[1000005], n;
string s, t;
void com_lps()
{
ll j = 0, i = 1;
lps[0] = 0;
while(i < n)
{
if(s[i] == s[j])
{
j ++;
lps[i] = j;
i ++;
}
else
{
if(j)
j = lps[j - 1];
else
{
lps[i] = 0;
i ++;
}
}
}
}
ll solve()
{
memset(match, 0, sizeof(match));
ll i = 0, j = 0;
while(i < n)
{
if(t[j] == s[i])
{
j ++;
match[i] = j;
i ++;
if(j == n)
return 0;
}
else
{
if(j)
j = lps[j - 1];
else
i ++;
}
}
return n - match[n - 1];
}
int main()
{
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n;
cin >> s;
cin >> t;
com_lps();
cout << solve();
// fclose(stdin);
// fclose(stdout);
return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 17;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
string s, p;
cin >> s >> p;
reverse(s.begin(), s.end());
for(int i = 0; ; i++){
if(string(s.rbegin(), s.rend()) == p)
return cout << i << '\n', 0;
s.pop_back();
p.pop_back();
}
}

Post a Comment

0 Comments