Cod sursa(job #1659105)

Utilizator KOzarmOvidiu Badea KOzarm Data 21 martie 2016 23:30:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char x[2000005],y[2000005];
int q,w,putere1,putere2,h1,h2,v1,v2,i,b1,b2,mod1,mod2,total;
struct nod
{
    int x;
    nod *next;
}*p,*ult;

void adauga(int x)
{
    nod *crt;
    if(p==NULL)
    {
        p=new nod;
        p->x=x;
        p->next=NULL;
        ult=p;
    }
    else
    {
        crt=new nod;
        crt->x=x;
        crt->next=NULL;
        ult->next=crt;
        ult=crt;
    }
}
int main()
{
    fin.getline(x,2000005);
    fin.getline(y,2000005);
    w=strlen(x);
    q=strlen(y);
    if(w>q)
    {
        fout<<0;
        return 0;
    }
    p=new nod;
    p=NULL;
    ult=p;
    b1=70;
    b2=b1;
    mod1=666013;
    mod2=100007;
    putere1=1;
    putere2=1;
    for(i=0;i<w;i++)
    {
        h1=(h1*b1+x[i])%mod1;
        h2=(h2*b2+x[i])%mod2;
        v1=(v1*b1+y[i])%mod1;
        v2=(v2*b2+y[i])%mod2;
        if(i!=0)
        {
            putere1=(b1*putere1)%mod1;
            putere2=(b2*putere2)%mod2;
        }
    }
    if(h1==v1&&h2==v2)
    {
        total++;
        adauga(0);
    }
    for(;y[i]!=0;i++)
    {
        v1=((v1-(y[i-w]*putere1)%mod1+mod1)*b1+y[i])%mod1;
        v2=((v2-(y[i-w]*putere2)%mod2+mod2)*b2+y[i])%mod2;
        if(h1==v1&&h2==v2)
        {
            total++;
            adauga(i-w+1);
        }
    }
    fout<<total<<"\n";
    for(nod *crt=p;crt!=NULL;crt=crt->next)
        fout<<crt->x<<" ";
    return 0;
}