Cod sursa(job #2838759)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 24 ianuarie 2022 16:02:59
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>
#define nmax (int)(1e6)+5
using namespace std;

ifstream in("granite.in");
ofstream out("granite.out");

vector<int> zalgo(){
    string s;
    in>>s;
    int n=s.size();
    int x=0,y=0;
    vector<int> z(n);
    for(int i=1;i<n;i++){
        z[i]=max(0,min(z[i-x],y-i+1));
        while(z[i]+i<n&&s[z[i]]==s[i+z[i]]){
            x=i;y=i+z[i];z[i]++;
        }
    }
    return z;
}

int main(){
    vector<int>z=zalgo();
    int n=z.size();
    int maxx=0,res1=0,res2=0;
    for(int i=0;i<n;i++){
        int s=min({z[i],i,(n-i)/2});
        for(int i=maxx+1;i<=s;i++){
            if(z[n-i]==i){
                res1++;
                res2=i;
            }
        }
        maxx=max(maxx,s);
    }
    out<<res1<<' '<<res2;
}