Cod sursa(job #1144817)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 17 martie 2014 17:24:08
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<vector>
#include<string>

using namespace std;

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

const int mod = 666013;

string a, b;
int v[ 1000 ];

inline int code( char c ) {
    if ( 'a' <= c && c <= 'z' ) {
        return c - 'A' + 26;
    } else {
        return c - 'A';
    }
}
int main()
{
    int p, ha, hb, sol, k;
    fin>>a>>b;
    sol = ha = hb = 0;
    p = 1;
    k = (int)a.size();

    if ( k < (int)b.size() ) {
        for( int i = k - 1; i >= 0; -- i ) {
            ha += p*code( a[i] );
            hb += p*code( b[i] );
            if ( i > 0 ) {
                p *= 52;
                p %= mod;
            }
        }
        if ( ha == hb ) {
            v[ 0 ] = 0;
            ++ sol;
        }
    }
    for( int i = k; i < (int)b.size(); ++ i ) {
        hb = ( hb - p * code( b[i-k] ) ) * 52 + code( b[i] );
        hb %= mod;
        if ( hb < 0 ) {
            hb += mod;
        }
        if ( ha == hb ) {
            if ( sol < 1000 )
                v[ sol ] = i - k + 1;
            ++ sol;
        }
    }

    fout<<sol<<'\n';

    sol = sol<1000?sol:1000;
    for( int i = 0; i < sol; ++ i ) {
        fout<<v[i]<<' ';
    }

    fin.close();
    fout.close();
    return 0;
}