Exact rotations needed to convert S into T

Question

0.00/5 (No votes)

See more:

Given two string S and T , I am allowed to do 2 operations. 1:delete the first character of the string S and 2. Append any character at the end of the string. How can I find the number of operations needed to convert S into T.I am quite a beginner so kindly help me

input:
7
aaxaabc
aabcaax

output: 3

But I am not getting 3 as my output

What I have tried:

C++

<pre>
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    char a[n];
    char b[n];
    char c[n];
    cin>>a>>b;
    char temp;
    int count=0;

    for(int i=0;i<n;i++){
        temp=a[0];
        a[i]=a[i+1];
        c[i]=a[i+1];
        c[n-1]=temp;
        
        if(strcmp(b,c)==0)
        break;
        else
        {
            count++;
            continue;
        }

    }
    
        cout<<count;
        cout<<endl;

}

Posted 22-Jun-19 3:11am

Noble Badass

Updated 22-Jun-19 4:23am

v2

Add a Solution

Comments

Patrice T 22-Jun-19 9:32am

"But I am not getting 3 as my output"
And what is your output ?

Noble Badass 22-Jun-19 9:41am

7

Patrice T 22-Jun-19 9:58am

This mean the your code never find a match.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2019-06-22T03:25:00

This is your homework, so I'm not going to give you any code!
Instead, I'll explain how to do it.
Start by inventing two strings, one called S and one called T. Write them down on a piece of paper, with T at the top and s below it.

Now, look at the first character of S: is it the same as the first character of T?
If it isn't, you will need to delete it.
If it is, is there another character in S?
If there is, is it the same as the second character in T? If it isn't, the first character will need deleting.
If it is, keep looking at both strings until you either get a difference (delete teh first character of S) or run out of S characters (great!)

If you ran out of S characters while matching, you need to append N characters from T to get the match.
If you got to the end of S before matching, you need to delete all S and append all T.

Try it on paper, you'll see what I mean. Try it with S = "ABBA", T = "BAT"

When you know how many to delete, and how many to append, you're done.
Now translate that to pseudo code, and then code and test it.
It's not really difficult if you just think it through carefully before you start coding, honest!

CPallini · Answer 2 · 2019-06-22T04:24:00

I assume you are talking about actual string rotations (as the title suggest). Note they are different from the 'allowed operations you described. Try

C++

using namespace std;


int check_rotate( char a[], char b[], size_t len)
{
  size_t n;
  for (n=0; n < len; ++n)
  {
    // compare
    if ( strncmp( a, b, len ) == 0 ) break;

    // rotate b
    char tmp = b[0];
    for ( size_t k=0; k<len-1;++k)
      b[k] = b[k+1];

    b[len-1] = tmp;

  }
  if ( n == len) return -1; // no match

  return (n <= len / 2 ? n : len-n); // return the minimum rotations required
}

int main()
{

  char a[] = "aaxaabc";
  char b[] = "aabcaax";
  const size_t len = sizeof(a)-1;

  int rot =  check_rotate(a,b,len);

  if ( rot >= 0)
    cout << "required rotations " << rot << endl;
  else
    cout << "no luck" << endl;
}

Patrice T · Answer 3 · 2019-06-22T03:54:00

Are you sure about description ?

Quote:
I am allowed to do 2 operations. 1:delete the first character of the string S and 2. Append any character at the end of the string.

This is not a rotation: From "aaxaabc", 3 times operation 1 makes "aabc" from description.

Quote:
But I am not getting 3 as my output

You have about 3 solutions:
- Pray the God of computer and await miracle.
- Look intensely at the code and expect to see the light.
- Watch the code preform until you spot where it go wrong. This activity is debugging.

I suspect your code to rotate wrong.
-----
Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.

Exact rotations needed to convert S into T

3 solutions

Solution 1

Solution 3

Solution 2

Add your solution here

Preview 0