Cod sursa(job #810921)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 11 noiembrie 2012 12:09:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <cstring>
#define  NMAX 2000004
#define  Fact 73
#define Disp1 100007
#define Disp2 100021

using namespace std;

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


int Rez[NMAX],Nr;
char A[NMAX],S[NMAX];
int Hash1,Hash2,SHash1,SHash2;


void Contor(int p)
{
    if(Nr>1000)return;
    Nr++;
    Rez[Nr] = p;
}

bool Verifica()
{
    if(Hash1 == SHash1 && Hash2 == SHash2)
        return 1;
    return 0;
}

int main()
{
    int N,M,i,F1 = 1,F2 = 1;
    in>>A;    N = strlen(A);
    in>>S;    M = strlen(S);

    for(i=0;i<N;i++)
    {
        Hash1 = (Hash1*Fact+A[i])%Disp1;
        Hash2 = (Hash2*Fact+A[i])%Disp2;
        if(i)F1*=Fact,F1%=Disp1,F2*=Fact,F2%=Disp2;
    }
    for(i=0;i<N;i++)
    {
        SHash1 = (SHash1*Fact+S[i])%Disp1;
        SHash2 = (SHash2*Fact+S[i])%Disp2;
    }
    if(Verifica())
        Contor(0);
    for(i=N;i<M;i++)
    {
        SHash1 = ((SHash1-(F1*S[i-N])%Disp1+Disp1)*Fact + S[i])%Disp1;
        SHash2 = ((SHash2-(F2*S[i-N])%Disp2+Disp2)*Fact + S[i])%Disp2;
        if(Verifica())
            Contor(i-N+1);
    }
    out<<Nr<<'\n';
    for(i=1;i<=Nr&&i<=1000;i++)
        out<<Rez[i]<<' ';
    return 0;
}