Cod sursa(job #2713414)

Utilizator MateGMGozner Mate MateGM Data 27 februarie 2021 21:17:40
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <vector>

using namespace std;

void build_kmp(vector<long long>&a,int n,vector<int>&t)
{
    for(int i=1;i<n;i++)
    {
        int k=t[i-1];
        while(true)
        {
            if(a[i]==a[k])
            {
                t[i]=k+1;
                break;
            }
            else if(k==0)
            {
                t[i]=0;
                break;
            }
            else {
                k=t[k-1];
            }
        }
    }
 //   return ans;
}

int main()
{
    ifstream be("reguli.in");
    ofstream ki("reguli.out");
    int n;
    be>>n;
    vector<long long>a;
    vector<long long>b(n);
    for(int i=0;i<n;i++)
    {
        be>>b[i];

        if(i>=1)
        {
            a.push_back(b[i]-b[i-1]);
        }
    }
    int m=a.size();
    vector<int>t(m,0);
    build_kmp(a,m,t);
    int ans=m-t[m-1];
    ki<<ans<<endl;
    for(int i=0;i<ans;i++)
        ki<<a[i]<<endl;
    return 0;
}