Cod sursa(job #2714085)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 1 martie 2021 11:54:38
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
/*
*  Created by Andrei Arhire 01/03/2021
*  Copyright © 2021 Andrei Arhire. All rights reserved.
*  Expected verdict - Accepted
*/
#include <bits/stdc++.h>

#define pb push_back
#define zero(pos) pos&(-pos)
#define eb emplace_back
#define mp make_pair
using namespace std;
const long long NR = 2e6 + 1e2;
const long long oo = 1e16;

string s , t ;
int p1 [ NR ] , p2 [ NR ] ;
int c1 = 31 , c2 = 37 ;
int MOD1 = 1e5 + 7 , MOD2 = 1e5 + 21;
vector < int > sol ;
ifstream in ("strmatch.in") ;
ofstream out ("strmatch.out") ;
signed main() {
    ios::sync_with_stdio(false);
    in.tie(nullptr);
    int i ;
    in >> s >> t ;
    if ( s.size() > t.size() )  {
        cout << "0\n" ;
        exit(0);
    }
    p1 [ 0 ] = 1 ;
    p2 [ 0 ] = 1 ;
    for ( i = 1 ; i <= t.size() ; ++ i ) {
        p1 [ i ] = ( 1LL * p1 [ i - 1 ] * c1 ) % MOD1 ;
        p2 [ i ] = ( 1LL * p2 [ i - 1 ] * c2 ) % MOD2 ;
    }
    int hash1 = 0 , hash2 = 0 ;
    for ( i = 0 ; i < s.size() ; ++ i ) {
        hash1 = 1LL * (hash1 + 1LL * (s[i] - 'A'+1)*p1[s.size()-i])%MOD1;
        hash2 = 1LL * (hash2 + 1LL * (s[i] - 'A'+1)*p2[s.size()-i])%MOD2;
    }
    int hash1t = 0 , hash2t = 0 ;

    for ( i = 0 ; i < s.size() ; ++ i ) {
        hash1t = 1LL *(hash1t + 1LL *(t[i] - 'A'+1)*p1[s.size()-i])%MOD1;
        hash2t = 1LL *(hash2t + 1LL *(t[i] - 'A'+1)*p2[s.size()-i])%MOD2;
    }
    if ( hash1 == hash1t && hash2 == hash2t )   {
        sol.pb( 0 ) ;
    }
    for ( i = s.size() ; i < t.size() ; ++ i ){
        hash1t = 1LL * (hash1t - 1LL * p1 [ s.size() ] * (t[i-s.size()]-'A'+1) %MOD1 + MOD1)%MOD1 + (t[i] - 'A'+1) ;
        hash1t = 1LL * hash1t * c1 % MOD1 ;
        hash2t = 1LL * (hash2t - 1LL * p2 [ s.size() ] * (t[i-s.size()]-'A'+1)%MOD2 + MOD2)%MOD2 + (t[i] - 'A'+1) ;
        hash2t = 1LL * hash2t * c2 % MOD2 ;
        if ( hash1 == hash1t && hash2 == hash2t )   {
            sol.pb( i - s.size() + 1 ) ;
        }
    }
    out << sol.size() << '\n' ;
    for ( i = 0 ; i < min ( 1000,(int) sol.size() ) ; ++ i ) {
        out << sol [ i ] << ' ' ;
    }
    out << '\n' ;
    return 0;
}