Cod sursa(job #1144332)

Utilizator Athena99Anghel Anca Athena99 Data 16 martie 2014 22:18:05
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <string>

using namespace std;

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

const int mod1= 666013;
const int mod2= 1000007;
const int base= 256;
const int nmax= 2000000;
const int solmax= 1000;

int sol[solmax+1];

int main(  ) {
    string a, b;
    fin>>a>>b;

    int h1= a[0], h2= a[0], bm1= 1, bm2= 1;
    for ( string::iterator it= a.begin()+1; it!=a.end(); ++it ) {
        h1= (h1*base+*it)%mod1, h2= (h2*base+*it)%mod2;
        bm1= (bm1*base)%mod1, bm2= (bm2*base)%mod2;
    }

    int x1= 0, x2= 0;
    for ( int i= 0; i<(int)a.size(); ++i ) {
        x1= (x1*base+b[i])%mod1, x2= (x2*base+b[i])%mod2;
    }

    if ( h1==x1 && h2==x2 ) {
        ++sol[0]; sol[sol[0]]= 1;
    }
    for ( int i= (int)a.size(); i<(int)b.size(); ++i ) {
        x1= (((x1-b[i-(int)a.size()]*bm1%mod1)*base+b[i])%mod1+mod1)%mod1;
        x2= (((x2-b[i-(int)a.size()]*bm2%mod2)*base+b[i])%mod2+mod2)%mod2;

        if ( h1==x1 && h2==x2 ) {
            ++sol[0]; 
            if ( sol[0]<=solmax ) {
                sol[sol[0]]= i-(int)a.size()+1;
            }
        }
    }

    fout<<sol[0]<<"\n";
    for ( int i= 1; i<=sol[0]; ++i ) {
        fout<<sol[i]<<" ";
    }
    fout<<"\n";

    return 0;
}