Original proposer: admin

Since the operation is a left shift of a string, applying it \(|A|\) times is an identical operation, so it is useless to perform it \(|A|\) or more times.
When \(k\) operations are performed against \(A\), it becomes \(A=B\) if and only if:

• the concatenation of the \((k+1)\)-th through the last characters, and then the first through \(k\)-th characters, of \(A\) before the operations equals \(B\).

Let us observe the specific behavior when representing the strings as \(A=\) ABCDE and \(B=\) pqrst.

• If ABCDE equals pqrst, the answer is \(0\).
• If BCDEA equals pqrst, the answer is \(1\).
• If CDEAB equals pqrst, the answer is \(2\).
• If DEABC equals pqrst, the answer is \(3\).
• If EABCD equals pqrst, the answer is \(4\).

If we can check all of them in \(O(N)\) time, the problem can be solved.
To check that, it is sufficient to determine the position of the first occurrence of pqrst in ABCDEABCD as a substring.

This is a well-known problem, asking to detect a specific pattern within a string.

While we can use rolling hashes or Suffix Array, here we will introduce a solution using Z-algorithm, which is available in ACL (AtCoder Library).

• First, apply Z-algorithm to a concatenation of \(B,A,A\) in this order. Let \(z\) be the resulting Z-array.
• In the example above, we perform the algorithm against \(S=\) pqrstABCDEABCDE.
• For \(k=0,1,\dots,|A|-1\), do the following.
  • Check if \(z[|A|+k] \ge |A|\).
  • If \(z[|A|+k] \ge |A|\), let \(k\) be the answer, and terminate the algorithm.
    • \(z[|A|+k]\) represents the length of the common prefix of \(S\), and the substring of \(S\) formed by \((|A|+k)\)-th characters and onward.
    • That \(z[|A|+k] \ge |A|\) means if you apply a left shift \(k\) times to \(A\), the resulting string equals \(B\).

Since Z-algorithm runs in \(O(|S|)\) time for a given string \(S\), the problem can be solved.

Sample code (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;
}