Cod sursa(job #1282313)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 4 decembrie 2014 00:57:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
//Deresu Roberto - FMI
//Re :)
#include<fstream>
#include<cstring>
#define mod1 12345
#define mod2 54321
#define p 26
#define nx 2000007
using namespace std;
int n,m,p1,p2,vala1,vala2,valb1,valb2,nrsol,sol[nx];
char a[nx],b[nx];

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int main()
{
    fin>>a>>b;
    m = strlen(a);
    n = strlen(b);

    p1 = p2 = 1;
    for(int i=0;i<m;i++)
    {
        vala1 = (vala1*p+a[i])%mod1;
        vala2 = (vala2*p+a[i])%mod2;

        valb1 = (valb1*p+b[i])%mod1;
        valb2 = (valb2*p+b[i])%mod2;
    }

    if(vala1 == valb1 && vala2 == valb2) sol[++nrsol] = 0;

    for(int i=1;i<m;i++)
    {
        p1 = (p1*p)%mod1;
        p2 = (p2*p)%mod2;
    }

    for(int i=m;i<n;i++)
    {
        valb1 = ((valb1 - (p1*b[i-m])%mod1+mod1)*p + b[i])%mod1;
        valb2 = ((valb2 - (p2*b[i-m])%mod2+mod2)*p + b[i])%mod2;

        if(vala1 == valb1 && vala2 == valb2) sol[++nrsol] = i;
    }

    fout<<nrsol<<'\n';

    if(nrsol>1000)
        nrsol = 1000;

    for(int i=1;i<=nrsol;i++)
        fout<<sol[i]<<" ";


	return 0;
}