Cod sursa(job #2372951)

Utilizator Bodo171Bogdan Pop Bodo171 Data 7 martie 2019 11:36:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=2*1000*1000+5;
string a,b;
int z[2*nmax];
int occ[1005];
int ans,i,r,c,n;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a>>b;
    n=a.size();
    a+=b;r=c=-1;
    for(i=1;i<a.size();i++)
    {
        if(i<r) z[i]=min(r-i,z[i-c]);
        if(z[i]<0) z[i]=0;
        while(a[i+z[i]]==a[z[i]]) z[i]++;
        if(i+z[i]>r) c=i,r=i+z[i];
        if(i>=n&&z[i]>=n)
        {
            ans++;
            if(ans<=1000)
                occ[ans]=i-n;
        }
        z[i]--;
    }
    g<<ans<<'\n';
    for(i=1;i<=min(ans,1000);i++)
        g<<occ[i]<<' ';
    return 0;
}