Cod sursa(job #2713195)

Utilizator WilIiamperWilliam Damian Balint WilIiamper Data 27 februarie 2021 13:48:07
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 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 ], letKey2[ 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, astrkey2 = 0;
    for ( int i = 0; i < a.size(); i++ ) {
        astrkey ^= letKey[ a[i] ];
        astrkey2 ^= letKey2[ a[i] ];
    }

    U64 key = 0, key2 = 0;
    for ( int i = 0; i < a.size(); i++ ) {
        key ^= letKey[ b[i] ];
        key2 ^= letKey2[ 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] ];

            key2 ^= letKey2[ b[i-len] ];
            key2 ^= letKey2[ b[i] ];
        }

        if ( key != astrkey || astrkey2 != key2 )
            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();
        letKey2[i] = (U64)rand() * (U64)rand();
    }
}

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

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