Cod sursa(job #629497)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 3 noiembrie 2011 14:11:42
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#define MOD 666013
#define B 73
using namespace std;
int sol[1002],n,m,hA,hB,k,putere;
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();
    hA=0; hB=0; putere=1;
    for(i=0;i<n;i++)
    {
        hA=(hA*B+a[i])%MOD;
        hB=(hB*B+b[i])%MOD;
        if(i!=n-1) putere=(putere*B)%MOD;
    }
    if(n>m) {fo<<"0\n"; return 0;}
    if(hA==hB) brute_force(0);
    for(i=1;i<=m-n+1;i++)
    {
        hB=((hB-((putere*b[i-1])%MOD)+MOD)*B+b[i+n-1])%MOD;
        if(hA==hB) brute_force(i);
    }
    fo<<k<<"\n";
    for(i=1;i<=k and i<=1000;i++) fo<<sol[i]<<" ";
    return 0;
}