Cod sursa(job #1148702)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 20 martie 2014 23:54:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream in( "strmatch.in" );
ofstream out( "strmatch.out" );
 
const int mod1 = 12974;
const int mod2 = 96235;
const int base = 256;
string a, b;
int v[1000];
int p1, p2, sol, k, ha1, ha2, hb1, hb2;

 
int main()
{
	int player_unu=0;
    in>>a>>b;
    sol = ha1 = ha2 = hb1 = hb2 = 0;
    p1 = p2 = 1;
    k = (int)a.size();
 
    if ( k <= (int)b.size() ) {
        for( int i = k - 1; i >= 0; -- i ) {
            ha1 += p1*a[i]; ha2 += p2*a[i];
            hb1 += p1*b[i]; hb2 += p2*b[i];
            ha1 %= mod1; hb1 %= mod1;
            ha2 %= mod2; hb2 %= mod2;
            if ( i > 0 ) {
                p1 *= base; p2 *= base;
                p1 %= mod1; p2 %= mod2;
            }
        }
        if ( ha1 == hb1 && ha2 == hb2 ) {
            v[ 0 ] = 0;
            ++ sol;
        }
    }
    for( int i = k; i < (int)b.size(); ++ i ) {
        hb1 = ( hb1 + mod1 - (p1 * b[i-k]) % mod1 ) * base + b[i];
        hb2 = ( hb2 + mod2 - (p2 * b[i-k]) % mod2 ) * base + b[i];
        hb1 %= mod1; hb2 %= mod2;
        if ( ha1 == hb1 && ha2 == hb2 ) {
            if ( sol < 1000 )
                v[ sol ] = i - k + 1;
            ++ sol;
        }
    }
 
    out<<sol<<'\n';
 
    if(sol>1000)
		sol = 1000;
    for( int i = 0; i < sol; ++ i ) {
        out<<v[i]<<' ';
    }
 
    return player_unu;
}