Pagini recente » Cod sursa (job #3342368) | Cod sursa (job #3342547) | Cod sursa (job #3352157) | Cod sursa (job #3309463) | Cod sursa (job #3329510)
/// https://www.infoarena.ro/automate-finite-si-kmp
#include <fstream>
#include <cstring>
using namespace std;
const int NMAX = 1e6 + 1;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
int n, a[NMAX], pi[NMAX], sol = NMAX;
void calcPrefix()
{
int x = 0;
pi[1] = 0;
for(int i = 2; i <= n; ++i)
{
while(x > 0 && a[x + 1] != a[i])
x = pi[x];
if(a[x + 1] == a[i])
++x;
pi[i] = x;
if(pi[i] > 0 && i % (i - pi[i]) == 0) sol = min(sol, i - pi[i]);
}
}
void citire()
{
fin >> n >> a[1];
for(int i = 2; i <= n; ++i)
{
fin >> a[i];
a[i - 1] = a[i] - a[i - 1];
}
--n;
}
void solutie()
{
calcPrefix();
fout << sol << "\n";
for(int i = 1; i <= sol; ++i) fout << a[i] << "\n";
}
int main()
{
citire();
solutie();
return 0;
}