Power Strings

#include "bits/stdc++.h"

/*
 * Author: Matheus Monteiro
 */

using namespace std;

// #ifdef DEBUGMONTEIRO
#define _ << " , " <<
#define bug(x) cout << #x << "  >>>>>>>  " << x << endl;
// #else
// #define bug(x)
// #endif

// #define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vii vector<ii>
#define LSOne(S) ((S) & (-S))
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

const int MAX = 200005;
// const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9;  //10^-9
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

vector<int> getZ(const string &s) {
  vector<int> z(s.size());
  int l = 0, r = 0;

  for(int i = 1; i < s.size(); ++i) {
    if(i < r) {
      z[i] = min(r - i, z[i - l]);
    }
    while(i + z[i] < s.size() && s[z[i]] == s[i + z[i]])
      z[i]++;
    if(i + z[i] > r) {
      l = i;
      r = i + z[i];
    }
  }
  return z;
}

void solve() {
  string s;
  while(cin >> s && s != ".") {
    auto z = getZ(s);
    int ans = 1;
    for(int i = 1; i < s.size(); ++i)
      if(i + z[i] >= s.size() && (s.size() % i == 0)) {
        ans = s.size() / i;
        break;
      }
    cout << ans << '\n';
  }
}

int32_t main() {
    fastio;

    int t = 1;
   // std::cin >> t;
    for(int caso = 1; caso <= t; ++caso) {
        //cout << "Case #" << caso << ": ";
        solve();
    }

    return 0;
}

/*
Before submit:
    Check the corners cases
    Check solution restrictions

For implementation solutions:
    Check the flow of the variables

For intervals problems:
    Think about two pointers

For complete search:
    Think about cuts

If you get WA:
    Reread your code looking for stupid typos
    Try various manual testcases
    Recheck the correctness of your algorithm
    Reread the statement
    Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
    Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
    Change the coder (if you're with a team)
    Give up. You may have other tasks to solve.
*/