Pagini recente » Cod sursa (job #2331166) | Cod sursa (job #2990892) | Cod sursa (job #2499413) | Cod sursa (job #2918856) | Cod sursa (job #18974)
Cod sursa(job #18974)
#include <stdio.h>
#define MAXN 500005
int N;
long long x[MAXN], s[MAXN];
int p[MAXN];
void prefix()
{
int i, k = 0;
p[1] = 0;
for (i = 2; i < N; i++)
{
for (; (k > 0) && (s[k + 1] != s[i]); )
k = p[k];
if (s[k + 1] == s[i])
k++;
p[i] = k;
}
}
void kmp()
{
int i, k = 0;
for (i = 1; i - N + 1 < N; i++)
{
for (; (k > 0) && (i < N && s[k + 1] != s[i]); )
k = p[k];
if (i >= N || s[k + 1] == s[i])
k++;
if (k == N - 1)
{
k = p[k];
if (i != N - 1)
{
printf("%d\n", i - N + 1);
for (k = 1; k <= i - N + 1; k++)
printf("%lld\n", s[k]);
return;
}
}
}
}
int main()
{
freopen("reguli.in", "rt", stdin);
freopen("reguli.out", "wt", stdout);
scanf("%d", &N);
int i;
for (i = 0; i < N; i++)
scanf("%lld", x + i);
for (i = 1; i < N; i++)
s[i] = x[i] - x[i - 1];
prefix();
kmp();
return 0;
}