Cod sursa(job #2713208)

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

#define LEN_MAX 2000000
#define mod 50021

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

string a, b;

typedef long long L64;

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() {

    L64 astrkey = 0;
    int Pow = 1;
    for ( int i = 0; i < a.size(); i++ ) {

        astrkey = ( astrkey * 300 + a[i] ) % mod;

        if ( i != 0 ) {
            Pow *= 300;
            Pow %= mod;
        }
    }

    L64 key = 0;
    for ( int i = 0; i < a.size(); i++ ) {
        key = ( key * 300 + b[i] ) % mod;
    }

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

        if ( i >= len ) {
            key = ( key - ( Pow * b[i-len] )%mod + mod ) % mod;
            key = ( key * 300 + b[i] ) % mod;
        }

        //fout << i << " " << key << " " << astrkey << "\n";
        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] << " ";
}


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

    RabinKarp();
    return 0;
}