Cod sursa(job #2714073)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 1 martie 2021 11:46:03
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 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 = 1e6 + 1e2;
const long long oo = 1e16;

string s , t ;
int p1 [ NR ] , p2 [ NR ] ;
int c1 = 31 , c2 = 37 ;
int MOD1 = 1e9 + 7 , MOD2 = 1e9+9;
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 ] = p1 [ i - 1 ] * c1 ;
        p2 [ i ] = p2 [ i - 1 ] * c2 ;
        p1 [ i ] %= MOD1 ;
        p2 [ i ] %= MOD2 ;
    }
    int hash1 = 0 , hash2 = 0 ;
    for ( i = 0 ; i < s.size() ; ++ i ) {
        hash1 = (hash1 + (s[i] - 'A'+1)*p1[s.size()-i])%MOD1;
        hash2 = (hash2 + (s[i] - 'A'+1)*p2[s.size()-i])%MOD2;
    }
    int hash1t = 0 , hash2t = 0 ;

    for ( i = 0 ; i < s.size() ; ++ i ) {
        hash1t = (hash1t + (t[i] - 'A'+1)*p1[s.size()-i])%MOD1;
        hash2t = (hash2t + (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 = (hash1t - p1 [ s.size() ] * (t[i-s.size()]-'A'+1) %MOD1 + MOD1)%MOD1 + (t[i] - 'A'+1) ;
        hash1t = hash1t * c1 % MOD1 ;
        hash2t = (hash2t - p2 [ s.size() ] * (t[i-s.size()]-'A'+1)%MOD2 + MOD2)%MOD2 + (t[i] - 'A'+1) ;
        hash2t = 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;
}