CSES - Shared codeLink to this code:
https://cses.fi/paste/91785ee2b5f0dd262517f4/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout << "----------------------------------\n";
#include <iostream>
int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}; // trick to explore an implicit 2D grid
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; // S,SE,E,NE,N,NW,W,SW neighbors //GO FOR EVEN FOR 4 moves
#define fastinput \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
vector<int> get_prefix(string s)
{
int i;
int len = s.length();
vector<int> pi(len, 0);
for (i = 1; i < len; i++)
{
int j = pi[i - 1];
while (j > 0 && s[i] != s[j])
{
//curently matche 'j'
j = pi[j - 1];
}
if (s[i] == s[j])
{
j++;
}
pi[i] = j;
}
return pi;
}
const int M = 1e6 + 1;
vector<int> adj[M];
vector<bool> vis(M, false);
vector<int> par(M, -1);
vector<int> tin(M, -1);
vector<int> tout(M, -1);
LL timer = 0;
void dfs(int s, int par_idx)
{
if (!vis[s])
{
vis[s] = true;
par[s] = par_idx;
// debug(s);
tin[s] = timer++;
for (auto &x : adj[s])
{
dfs(x, par_idx);
}
tout[s] = timer++;
}
}
int main()
{
fastinput;
LL n, i, j, k, temp, tc;
string s, t;
cin >> s;
vector<int> pi = get_prefix(s);
int len = s.length();
// debug(len);
// for (auto &x : pi)
// {
// cout << x << " ";
// }
// cout << endl;
// part;
for (i = 0; i < len; i++)
{
par[i] = i;
}
for (i = 0; i < len; i++)
{
int curr_idx = i;
int prev = pi[i] - 1;
if (prev != -1)
{
adj[curr_idx].pb(prev);
adj[prev].pb(curr_idx);
// cout << "edge between " << prev << " " << curr_idx << endl;
}
}
for (i = 0; i < len; i++)
{
if (!vis[i])
{
// cout << "parent " << i << endl;
dfs(i, i);
}
}
// debug(len);
////////////
// cout << "parent is " << endl;
// for (i = 0; i < len; i++)
// {
// cout << par[i] << " ";
// }
// part;
// part;
auto is_ch_par = [&](int x, int y)
{
if (par[x] != par[y])
{
return false;
}
return (tin[x] >= tin[y] && tout[x] <= tout[y]);
};
for (i = 0; i < len; i++)
{
//seeing if this will be successful
int now_len = i + 1;
bool poss = true;
// debug(i);
// debug(now_len);
for (j = 0; j + now_len <= len; j += now_len)
{
int last_idx = j + now_len - 1;
if (!is_ch_par(last_idx, i))
{
// cout << "not match at " << last_idx << endl;
poss = false;
break;
}
else
{
// cout << "match " << last_idx << endl;
}
}
int rem = len % now_len;
if (rem != 0)
{
// debug(rem);
if (!is_ch_par(len - 1, rem - 1))
{
// cout << "failure at end" << endl;
poss = false;
}
}
if (poss)
{
int ans = i + 1;
cout << i + 1 << " ";
// debug(ans);
}
// part;
// part;
}
return 0;
}
/*
Print your solution! Print debug output, as well.
> Are you clearing all datastructures between test cases?
> Can your algorithm handle the whole range of input?
> Read the full problem statement again.
> Any uninitialized variables?
> look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)
*/