Chương trình kiểm tra hai chuỗi có phải xoay vòng của nhau không

Ở đây chúng ta sẽ xem một chương trình có thể cho biết hai chuỗi có phải là xoay vòng của nhau hay không. Xoay vòng của chuỗi giống như:

Giả sử hai chuỗi là S1 = 'HELLO', và S2 = 'LOHEL'. Vì vậy chúng là xoay vòng của nhau. Bằng cách xoay HELLO ba vị trí sang trái nó sẽ thành LOHEL.

Để giải quyết bài toán này, chúng ta sẽ nối chuỗi đầu tiên với chính nó, sau đó kiểm tra xem chuỗi thứ hai có xuất hiện trong chuỗi nối hay không. Vì vậy với HELLO, nó sẽ là HELLOHELLO. Chuỗi nối này chứa LOHEL. [HELLOHELLO].

Thuật toán

isRotation(str1, str2)

begin
  if lengths of str1, and str2 are not same then return false;
  temp := concatenate str1 with str1 itself
  if temp contains str2, then
    return true
  otherwise return false
end

Ví dụ

#include<iostream>
using namespace std;

bool isRotation(string str1, string str2){
  if(str1.length() != str2.length())
    return false;
  string con_str = str1 + str1;
  if(con_str.find(str2) != string::npos){
    return true;
  } else {
    return false;
  }
}

main() {
  string str1, str2;
  cout << "Enter two strings: ";
  cin >> str1 >> str2;
  if(isRotation(str1, str2)){
    cout << "Two strings are rotation of each other";
  } else {
    cout << "Two strings are not rotation of each other";
  }
}

Kết quả

Enter two strings: STACK CKSTA
Two strings are rotation of each other