Cod sursa(job #2422099)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 17 mai 2019 11:08:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#define B1 59
#define B2 61
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string x,y;
int n,m,sol[1005],i,nr;
long long p1,p2,v1,v2,h1,h2;
const long long MOD1=1e9+7,MOD2=666013;
int main()
{
    f>>x>>y;
    m=x.size();
    n=y.size();
    if(m>n)
    {
        g<<0;
    }
    else
    {
        p1=p2=1;
        v1=v2=0;
        for(i=0;i<m;i++)
        {
            v1=(v1*B1+x[i])%MOD1;
            v2=(v2*B2+x[i])%MOD2;
            if(i!=1)
            {
                p1=(p1*B1)%MOD1;
                p2=(p2*B2)%MOD2;
            }
        }
        h1=h2=0;
        for(i=0;i<m;i++)
        {
            h1=(h1*B1+y[i])%MOD1;
            h2=(h2*B2+y[i])%MOD2;
        }
        if(h1==v1 && h2==v2)
        {
            nr++;
            sol[nr]=0;
        }
        for (i=m; i<n; i++)
        {
            h1=((h1-(y[i - m]*p1)%MOD1+MOD1)*B1+y[i])%MOD1;
            h2=((h2-(y[i - m]*p2)%MOD2+MOD2)*B2+y[i])%MOD2;
            if (h1==v1 && h2==v2)
            {
                nr++;
                if(nr<=1000)
                {
                    sol[nr]=i-m+1;
                }
            }
        }
        g<<nr<<"\n";
        for(i=1;i<=nr;i++)
        {
            g<<sol[i]<<" ";
        }
    }
    return 0;
}