Submission #3770304

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

template <typename T>
vector<int> kmp_table(int n, const T& s) {
  vector<int> p(n);
  int k = 0;
  for (int i = 1; i < n; ++i) {
    while (k > 0 && s[i] != s[k]) {
      k = p[k - 1];
    }
    if (s[i] == s[k]) {
      ++k;
    }
    p[i] = k;
  }
  return p;
}

template <typename T>
vector<int> kmp_table(const T& s) {
  return kmp_table((int) s.size(), s);
}

template <typename T>
vector<int> kmp_search(int n, const T& s, int m, const T& w, const vector<int>& p) {
  assert(n >= 1 && (int) p.size() == n);
  vector<int> ret;
  int k = 0;
  for (int i = 0; i < m; ++i) {
    while (k > 0 && (k == n || w[i] != s[k])) {
      k = p[k - 1];
    }
    if (w[i] == s[k]) {
      ++k;
    }
    if (k == n) {
      ret.push_back(i - n + 1);
    }
  }
  return ret;
}

template <typename T>
vector<int> kmp_search(const T& s, const T& w, const vector<int>& p) {
  return kmp_search((int) s.size(), s, (int) w.size(), w, p);
}

int main() {
  string s;
  cin >> s;
  int n = (int) s.size();
  vector<bool> f(n), g(n);
  for (int rot = 0; rot < 2; ++rot) {
    auto& v = rot == 0 ? f : g;
    auto p = kmp_table(s);
    for (int i = 0; i < n; ++i) {
      v[i] = (p[i] == 0 || (i + 1) % (i + 1 - p[i]) != 0);
    }
    reverse(s.begin(), s.end());
  }
  if (f[n - 1]) {
    cout << "1\n1\n";
    return 0;
  }
  int split = 0;
  for (int i = 0; i < n; ++i) {
    if (f[i] && g[n - 1 - i]) {
      ++split;
    }
  }
  if (split == 0) {
    cout << n << '\n' << 1 << '\n';
  } else {
    cout << 2 << '\n' << split << '\n';
  }
  return 0;
}

Submission Info

Judge Result