Cod sursa(job #2714157)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 1 martie 2021 13:09:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 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 = 73 ;
int c2 = 71 ;
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() )  {
        out << "0\n" ;
        return 0 ;
    }
    p1 [ 0 ] = 1 ;
    p2 [ 0 ] = 1 ;
    for ( i = 1 ; i <= s.size() ; ++ i ) {
        p1 [ i ] = ( p1 [ i - 1 ] * c1 ) % MOD1 ;
        p2 [ i ] = (  p2 [ i - 1 ] * c2 ) % MOD2 ;
    }
    int hash1 = 0 , hash2 = 0 ;
    int hash1t = 0 , hash2t = 0 ;
    for ( i = 0 ; i < s.size() ; ++ i ) {
        hash1 = ( hash1 * c1 + (s[i]) ) % MOD1 ;
        hash2 = ( hash2 * c2 + (s[i] ) ) % MOD2 ;
        hash1t = ( hash1t * c1 + (t[i]) ) % MOD1 ;
        hash2t = ( hash2t * c2 + (t[i] ) ) % MOD2 ;
    }

    if ( hash1 == hash1t && hash2 == hash2t )   {
        sol.pb( 0 ) ;
    }
    for ( i = s.size() ; i < t.size() ; ++ i ){
        hash1t =( (hash1t -  (p1 [ s.size() - 1 ] * t[i-s.size()]) %MOD1 + MOD1 ) * c1 + t[i] ) % MOD1 ;
        hash2t = ( (hash2t - (p2 [ s.size() - 1 ] * t[i-s.size()]) %MOD2 + MOD2 ) * c2  + t[i] ) % 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;
}