Cod sursa(job #2713405)

Utilizator MateGMGozner Mate MateGM Data 27 februarie 2021 21:03:46
Problema Reguli Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <vector>

using namespace std;

int build_kmp(vector<long long>&a,int n)
{
    int ans=0;
    vector<int>t(n,0);
    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];
            }
        }
        int hossz=i-t[i]+1;
        if(t[i] && !((i+1)%hossz))
            ans=max(ans,t[i]);
    }
    return ans;
}

int main()
{
    ifstream be("reguli.in");
    ofstream ki("reguli.out");
    int n;
    be>>n;
    vector<long long>a(n);
    vector<long long>b(n);
    for(int i=0;i<n;i++)
    {
        be>>b[i];
    }
    for(int i=0;i<n-1;i++)
        a[i]=b[i+1]-b[i];
    int ans=build_kmp(a,n);
    ki<<ans<<endl;
    for(int i=0;i<ans;i++)
        ki<<a[i]<<endl;
    return 0;
}