Cod sursa(job #2395404)

Utilizator AndreiTudorSpiruAndrei Spiru AndreiTudorSpiru Data 2 aprilie 2019 14:33:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000010],b[2000010];
int n,m,i,k,nr,p[2000010],ans[1010];
int main()
{
    f>>(a+1);
    f>>(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    /*for(i=n-1; i>=0; i--)
        a[i+1]=a[i];
    for(i=m-1; i>=0; i--)
        b[i+1]=b[i];
    a[0]=b[0]=0;*/
    k=0;


    for(i=2; i<=n; i++)
    {
        while(k!=0&&a[k+1]!=a[i])k=p[k];
        if(a[k+1]==a[i])k++;
        p[i]=k;
    }
    k=0;
    for(i=1; i<=m; i++)
    {
        while(k!=0&&a[k+1]!=b[i])k=p[k];
        if(a[k+1]==b[i])k++;
        if(k==n)
        {
            k=p[k];
            nr++;
            if(nr<=1000)
            ans[nr]=i-n;
        }

    }
    g<<nr<<'\n';
    for(i=1;i<=min(nr,1000);i++)
    {
        g<<ans[i]<<" ";
    }
    return 0;
}