Cod sursa(job #2183908)

Utilizator Athena99Anghel Anca Athena99 Data 23 martie 2018 16:08:12
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int base= 256;
const int mod1= 666013;
const int mod2= 123451;

int n;

string a, b;
vector <int> sol;

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

    if ( (int)a.size()>(int)b.size() ) {
        fout<<"0\n";
        return 0;
    }

    int h1= 0, h2= 0, p1= 1, p2= 1;
    for ( int i= 0; i<(int)a.size(); ++i ) {
        h1= (h1*base+a[i])%mod1;
        h2= (h2*base+a[i])%mod2;

        if ( i>0 ) {
            p1= (p1*base)%mod1;
            p2= (p2*base)%mod2;
        }
    }

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

    if ( b1==h1 && b2==h2 ) {
        ++n;
        sol.push_back(0);
    }

    for ( int i= (int)a.size(); i<(int)b.size(); ++i ) {
        b1= (((b1-b[i-(int)a.size()]*p1)*base+b[i])%mod1+mod1)%mod1;
        b2= (((b2-b[i-(int)a.size()]*p2)*base+b[i])%mod2+mod2)%mod2;

        if ( b1==h1 && b2==h2 ) {
            ++n;
            if ( n<=1000 ) {
                sol.push_back(i-(int)a.size()+1);
            }
        }
    }

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

    return 0;
}