SAM的时间复杂度在这道题是很玄学的，并且可以在刻意的构造数据下被卡掉。

数据生成器：

int main() {
  std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout << 1 << endl;
  int n = 1e5, kk = n / 3;
  for (int i = 1; i <= n; i++) {
    if (i % kk) {
      cout << 'A';
    } else {
      cout << 'C';
    }
  }
  cout << endl;
  for (int i = 1; i < kk; i++) {
    cout << 'A';
  }
  cout << 'C' << endl;
  return 0;
}

本机上跑题解区内的三篇SAM题解和自己写的SAM做法都可以被卡成TLE。