2つの文字列が互いの回転かどうかを判定するC++プログラムの解説

本記事では、2つの文字列が互いに回転関係にあるかどうかを判定できるプログラムを紹介します。

文字列の回転とは

文字列の「回転」とは、先頭の文字を末尾へ移動させる操作（またはその逆）を繰り返すことで得られる文字列のことです。例として、S1 = 'HELLO'、S2 = 'LOHEL' という2つの文字列を考えてみましょう。

HELLO を左方向に3文字分回転させると LOHEL になるため、この2つの文字列は互いの回転であるといえます。

解法のアプローチ

この問題は、とてもシンプルな考え方で解決できます。手順は以下の通りです。

1. 1つ目の文字列を、それ自身と連結します。
2. 連結後の文字列の中に、2つ目の文字列が部分文字列として含まれているかどうかを確認します。

具体的には、HELLO を自分自身と連結すると HELLOHELLO になります。この中には LOHEL が含まれています（HELLOHELLO）。これは、元の文字列をどれだけ回転させたものであっても、必ずその2倍の長さの連結文字列の中に現れるためです。

アルゴリズム

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

まず2つの文字列の長さが等しいかを確認し、異なる場合は即座に false を返します。長さが同じであれば、str1 を自己連結した文字列 temp を作成し、temp 内に str2 が存在するかを調べます。

C++での実装例

#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";
   }
}

実行結果

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

入力された STACK と CKSTA は互いの回転関係にあるため、「Two strings are rotation of each other（2つの文字列は互いの回転です）」と出力されます。

まとめ

この手法のポイントは、文字列を自己連結すると、そのすべての回転パターンが部分文字列として現れるという性質を利用することです。計算量は文字列検索に依存しますが、実装が非常に簡単で実用的なアプローチといえます。