MAXMATCH - Maximum Self-Matching

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
struct complex_t {
  double a {0.0}, b {0.0};
  complex_t(){}
  complex_t(double na) : a{na}{}
  complex_t(double na, double nb) : a{na}, b{nb} {}
  const complex_t operator+(const complex_t &c) const {
    return complex_t(a + c.a, b + c.b);
  }
  const complex_t operator-(const complex_t &c) const {
    return complex_t(a - c.a, b - c.b);
  }
  const complex_t operator*(const complex_t &c) const {
    return complex_t(a*c.a - b*c.b, a*c.b + b*c.a);
  }
  const complex_t operator/(const int &c) const {
    return complex_t(a/c, b/c);
  }
};
using cd = complex_t;
const double PI = acos(-1);
void fft(vector<cd> & a, bool invert) {
  int n = a.size();
  for (int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    for (; j & bit; bit >>= 1)
      j ^= bit;
    j ^= bit;
    if (i < j)
      swap(a[i], a[j]);
  }
  for (int len = 2; len <= n; len <<= 1) {
    double ang = 2 * PI / len * (invert ? -1 : 1);
    cd wlen(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      cd w(1);
      for (int j = 0; j < len / 2; j++) {
        cd u = a[i+j], v = a[i+j+len/2] * w;
        a[i+j] = u + v;
        a[i+j+len/2] = u - v;
        w = w * wlen;
      }
    }
  }
  if (invert) {
    for (cd & x : a){
      x = x / n;
    }
  }
}
vector<ll> multiply(vector<int> const& a, vector<int> const& b) {
  vector<cd> fa(a.begin(), a.end());
  vector<cd> fb(b.begin(), b.end());
  int n = 1;
  while(n < int(a.size() + b.size()) )
    n <<= 1;
  fa.resize(n);
  fb.resize(n);
  fft(fa, false);
  fft(fb, false);
  for (int i = 0; i < n; i++)
    fa[i] = fa[i]*fb[i];
  fft(fa, true);
  vector<ll> result(n);
  for (int i = 0; i < n; i++)
    result[i] = round(fa[i].a);
  return result;
}

vector<long long> getC(string s, char ch) {
  int n = s.size();

  vector<int> a(n, 0), b(n, 0);
  for (int i = 0; i < n; ++i) {
    if (s[i] == ch) {
      a[i] = 1;
      b[i] = 1;
    }
  }

  reverse(a.begin(), a.end());
  for (int i = 0; i < n; ++i) {
    a.push_back(0);
  }

  for (int i = 0; i < n; ++i) {
    b.push_back(b[i]);
  }

  vector<long long> c = multiply(a, b);

  // for (int i = 0; i < (int)c.size(); ++i) {
  //   cout << c[i] << " \n"[i==(int)c.size()-1];
  // }

  return c;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  string s; cin >> s;
  int n = s.size();

  vector<long long> c1 = getC(s, 'a');
  vector<long long> c2 = getC(s, 'b');
  vector<long long> c3 = getC(s, 'c');

  long long mx = 0;
  for (int i = 2 * n; i < 2 * n + n - 1; ++i) {
    //cout << c1[i] << '\n';
    mx = max(mx, c1[i] + c2[i] + c3[i]);
  }

  vector<int> ans;
  for (int i = 2 * n, j = 1; i < 2 * n + n - 1; ++i, ++j) {
    if (mx == c1[i] + c2[i] + c3[i]) {
      ans.push_back(j);
    }
  }

  cout << mx << '\n';
  for (int i = 0; i < (int)ans.size(); ++i) {
    cout << ans[i] << " \n"[i==(int)ans.size()-1];
  }
}