items on it.
is selling electric telephones, and manufactures his wares on a conveyor belt, which hasWhen his conveyor belt shifts right once, the rightmost item is removed and re-added to the left. When his conveyor belt shifts left once, the leftmost item is removed and is re-added to the right.
After watching his conveyor belt rotate for hours in this manner,
wants to know the minimum number of shifts it will take for his conveyor belt to start from a given position and end at a different position.Wanting to stop
from spending even more time watching his conveyor belt, you will write a program to compute the answer!Input Specification
The first line will consist of one integer, , representing the length of the conveyor belt.
The second line will have a string of length , representing the starting position of the conveyor belt.
The third line will have a string of length , representing the ending position of the conveyor belt.
Output Specification
Your program should output the minimum number of shifts that it will take to transform the starting position of the conveyor belt to match the end position.
If it is possible for the conveyor belt to be shifted to match the end position, the output of the program should be two characters. The first should be the direction that the conveyor belt must move in (L
representing left, and R
representing right - if it takes the same number of shifts in either direction to reach the end position output L
), and the second should be the number of shifts that must be performed.
If it is impossible to shift the conveyor belt to match the end position, output -1
.
Sample Input 1
6
abcdef
cdefab
Sample Output 1
L2
Explanation of Sample Output 1
If the conveyor belt is rotated two times to the left from its starting position, it will match the end position.
Sample Input 2
6
abcdef
cdefac
Sample Output 2
-1
Explanation of Sample Output 2
No matter how the conveyor belt is rotated, it will never match the given end position.
Comments
Does this mean that it will only shift 9 at most?