Cod sursa(job #2657132)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 9 octombrie 2020 18:28:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <vector>
using namespace std;
const long long baza = 999999937;
const long long m = 999999931;
vector<long long> v;
long long rasp;
string a, b;

int main()
{
    cin >> a >> b;
    if( a.size() > b.size() ){
        printf( "0\n" );
    } else {
        long long vala = 0;
        long long valb = 0;
        long long put = 1, i;
        for( i = 0; i < a.size(); i++ ){
            vala = (  vala * baza + a[ i ] ) % m;
            put = ( put * baza ) % m;
        }
        for( i = 0; i < a.size(); i++ )
            valb = ( valb * baza + b[ i ] ) % m;
        if( vala == valb ){
            ++rasp;
            v.push_back( 0 );
        }
        for( i = 1; i <= b.size() - a.size(); i++ ){
            valb = ( valb * baza + b[ i + a.size() - 1 ] ) % m;
            long long ceva = ( put * b[ i - 1 ] ) % m;
            valb = ( valb - ceva + m ) % m;
            if( vala == valb ){
                ++rasp;
                if( v.size() < 1000 )
                    v.push_back( i );
            }
        }
        printf( "%lld\n", rasp );
        for( i = 0; i < v.size(); i++ )
            printf( "%lld ", v[ i ] );
        printf( "\n" );
    }
    return 0;
}