Cod sursa(job #1932384)

Utilizator darian2001Clodnischi Darian Antonio darian2001 Data 19 martie 2017 18:42:33
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
using namespace std;

ifstream f("reguli.in");
ofstream g("reguli.out");

long long n,sir[500000];
long long pi[500000];

void KMP()
{
    int j=1,elemMax=n;
    for(int i=2;i<=n;i++)
    {
        while(j>1&&sir[i]!=sir[j])
            j=pi[j-1];
        if(sir[i]==sir[j])
            j++;
        pi[i]=j-1;
    }
    if(pi[n]>=n-pi[n])
    elemMax=elemMax-pi[n];
    g<<elemMax<<"\n";
    for(int i=1;i<=elemMax;i++)
        g<<sir[i]<<"\n";
}

int main()
{
    f>>n;
    long long first,nr;
    f>>first;
    for(int i=1;i<n;i++)
    {
        f>>nr;
        sir[i]=nr-first;

        first=nr;
    }
    n--;
    KMP();
    f.close();
    g.close();
}