「\(S\) の先頭 \(k\) 文字と末尾 \(k\) 文字とが一致する」という条件は、 ACL 二も実装されている Z-algorithm を利用することで直接判定できます。

これで問題文の指示にある配列 \(d\) を直接構築し、問題文の指示に従って出力すればよいです。

本解法の時間計算量はテストケースあたり \(O(|S|)\) です。

実装例 (C++):

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

using namespace std;
using namespace atcoder;

int main(){
  int Q;
  cin >> Q;
  while(Q--){
    string S;
    cin >> S;
    int n=S.size();
    auto z=z_algorithm(S);
    vector<int> d;
    for(int i=n-1;i>=1;i--){
      if(z[i]==(n-i)){d.push_back(n-i);}
    }
    if(d.size()==0){cout << "0\n";}
    else if(d.size()==1){cout << d[0] << "\n";}
    else{
      int ans=(d[1]-d[0]);
      for(int i=2;i<d.size();i++){
        ans=gcd(ans,d[i]-d[i-1]);
      }
      cout << ans << "\n";
    }
  }
  return 0;
}