問題原案：admin

操作は文字列の左シフトであるため、 \(|A|\) 回操作をすると文字列が元に戻るので、 \(|A|\) 回以上の操作を行う必要はありません。
\(A\) に操作を \(k\) 回行った時、 \(A=B\) となる条件は次の通りです。

• 操作前の \(A\) の \(k+1\) 文字目から末尾まで、操作前の \(A\) の \(1\) 文字目から \(k\) 文字目までをこの順に連結した文字列が、 \(B\) と等しい

各文字を \(A=\) ABCDE 、 \(B=\) pqrst と置いた例で考えてみましょう。

• ABCDE と pqrst が等しいなら、答えは \(0\) である。
• BCDEA と pqrst が等しいなら、答えは \(1\) である。
• CDEAB と pqrst が等しいなら、答えは \(2\) である。
• DEABC と pqrst が等しいなら、答えは \(3\) である。
• EABCD と pqrst が等しいなら、答えは \(4\) である。

これを全部まとめて \(O(N)\) などの計算量で解ければこの問題に正解できます。
この判定を行うには ABCDEABCD のうち pqrst が最初にどこに部分文字列として出現するか判定すればよいです。

このような文字列中の特定のパターンを検出する問題はよく知られています。

ローリングハッシュや Suffix Array などによる解法もありますが、ここでは ACL にも実装されている Z-algorithm による解法を紹介します。

• まず、 \(B,A,A\) をこの順に連結した文字列 \(S\) を Z-algorithm にかけ、解答である Z-array \(z\) を取得する。
• 例では、 \(S=\) pqrstABCDEABCDE となる。
• \(k=0,1,\dots,|A|-1\) について以下を繰り返す。
  • \(z[|A|+k] \ge |A|\) か判定する。
  • もし \(z[|A|+k] \ge |A|\) であれば答えは \(k\) として終了する。
    • \(z[|A|+k]\) は \(S\) の接頭辞と \(S\) の \(|A|+k\) 文字目以降を切り抜いた部分文字列とが何文字目まで一致するかを表します。
    • \(z[|A|+k] \ge |A|\) であるということは、 \(A\) を\(k\) 回左シフトした文字列と \(B\) が一致することを表します。

Z-algorithm は与える文字列を \(S\) として時間計算量 \(O(|S|)\) で動作するため、この問題に正解することができます。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    string a,b;
    cin >> a >> b;
    int l=a.size();
    string s=b+a+a;
    auto z=z_algorithm(s);
    bool ok=false;
    for(int k=0;k<l;k++){
      if(z[l+k]>=l){
        ok=true;
        cout << k << "\n";
        break;
      }
    }
    if(!ok){cout << "-1\n";}
  }
  return 0;
}