Cod sursa(job #629516)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 3 noiembrie 2011 14:19:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#define MOD1 666013
#define MOD2 100021
#define B 73
using namespace std;
int sol[1002],n,m,hA1,hA2,hB1,hB2,k,putere1,putere2;
string a,b;
void brute_force(int p)
{
    int i;
    bool ok=1;
//    for(i=p;i<=p+n-1;i++)
//    if(a[i-p]!=b[i]) {ok=0; break;}
    if(ok and k<1000) sol[++k]=p; else if(ok) k++;
}
int main()
{
    int i;
    ifstream fi("strmatch.in");
    ofstream fo("strmatch.out");
    fi>>a;
    fi>>b;
    n=a.size();
    m=b.size();
    hA1=hB1=hB2=hA2=0; putere1=putere2=1;
    for(i=0;i<n;i++)
    {
        hA1=(hA1*B+a[i])%MOD1;
        hA2=(hA2*B+a[i])%MOD2;
        hB1=(hB1*B+b[i])%MOD1;
        hB2=(hB2*B+b[i])%MOD2;
        if(i!=n-1) putere1=(putere1*B)%MOD1;
        if(i!=n-1) putere2=(putere2*B)%MOD2;
    }
    if(n>m) {fo<<"0\n"; return 0;}
    if(hA1==hB1 and hA2==hB2) brute_force(0);
    for(i=1;i<=m-n+1;i++)
    {
        hB1=((hB1-((putere1*b[i-1])%MOD1)+MOD1)*B+b[i+n-1])%MOD1;
        hB2=((hB2-((putere2*b[i-1])%MOD2)+MOD2)*B+b[i+n-1])%MOD2;
        if(hA1==hB1 and hA2==hB2) brute_force(i);
    }
    fo<<k<<"\n";
    for(i=1;i<=k and i<=1000;i++) fo<<sol[i]<<" ";
    return 0;
}