Cod sursa(job #2574362)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 5 martie 2020 21:50:38
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <algorithm>

const int NMAX=750005;

using namespace std;

ifstream cin("potriveala.in");
ofstream cout("potriveala.out");

int z1[NMAX],z2[NMAX];

void z(string s)
{
    int r=0,pozr=0;
    for(int i=1; i<(int)s.size(); ++i)
    {
        if(i>r)
        {
            while(i+z2[i]<(int)s.size() && s[i+z2[i]]==s[z2[i]])
                z2[i]++;
        }
        else
        {
            int leftover=min(z2[i-pozr],r-i);
            z2[i]=leftover;
            while(i+z2[i]<(int)s.size() && s[i+z2[i]]==s[z2[i]])
                z2[i]++;
        }
        if(i+z2[i]>r)
        {
            r=i+z2[i];
            pozr=i;
        }
    }
}

void copy_pref(int n)
{
    for(int i=0; i<=n; ++i)
    {
        z1[i]=z2[i];
        z2[i]=0;
    }
}
int main()
{
    string a,b;
    cin>>a>>b;
    string s1=b;
    while((int)s1.size()<(int)a.size())
        s1+=b;
    string s2=s1;
    s1+="#";
    s1+=a;
    z(s1);
    copy_pref((int)s1.size());
    reverse(s2.begin(),s2.end());
    int cnt=(int)s2.size();
    s2+="#";
    reverse(a.begin(),a.end());
    s2+=a;
    z(s2);
    int sol=0;
    for(int i=cnt+1; i<(int)s2.size(); ++i)
        sol=max(sol,z1[i]+z2[(int)s2.size()-i+cnt+1]);
    cout<<sol<<'\n';
    return 0;
}