Cod sursa(job #2713192)

Utilizator WilIiamperWilliam Damian Balint WilIiamper Data 27 februarie 2021 13:44:28
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <string>
#include <cstdlib>

#define LEN_MAX 2000000

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

string a, b;

typedef unsigned long long U64;

U64 letKey[ 300 ];
int index[ 1010 ], ans;

bool Matching ( int sIndex ) {

    for ( int i = 0; i < a.size(); i++ ) {
        if ( a[ i ] != b[ sIndex+i ] )
            return false;
    }
    return true;
}

void RabinKarp() {

    U64 astrkey = 0;
    for ( int i = 0; i < a.size(); i++ )
        astrkey ^= letKey[ a[i] ];

    U64 key = 0;
    for ( int i = 0; i < a.size(); i++ )
        key ^= letKey[ b[i] ];

    int len = a.size();
    for ( int i = len - 1; i < b.size(); i++ ) {

        if ( i >= len ) {
            key ^= letKey[ b[i-len] ];
            key ^= letKey[ b[i] ];
        }

        if ( key != astrkey )
            continue;

        if ( Matching( i-len+1 ) ) {
            ans++;
            if ( ans <= 1000 )
                index[ ans ] = i-len+1;
        }
    }

    fout << ans << "\n";
    for ( int i = 1; i <= min(ans, 1000); i++ )
        fout << index[i] << " ";
}

void init () {

    for ( int i = 0; i < 300; i++ ) {
        letKey[i] = (U64)rand() * (U64)rand();
    }
}

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

    init();
    RabinKarp();
    return 0;
}