Cod sursa(job #2641279)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 10 august 2020 21:00:12
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.61 kb
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lll long long
#define llf __float128
#define lld long double
using namespace std;
const int NR = 2e6 + 10  ,oo = 2e9 + 10, MOD1 = 1e9 + 7 , MOD2 = 1e9 + 9 ;
const long double pi = 2*acos(0.0);

string s1 , s2 ;
int fact1 [ NR ] , fact2 [ NR ] , temp1 , temp2 , cnt , temp10 , temp20 , val ;
vector < int > sol ;
int real_val [ 260 ] ;
ifstream in ("strmatch.in") ;
ofstream out ("strmatch.out") ;

signed main () {
    int i , hash1 = 0 , j , hash2 = 0 ;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0) ;


    in >> s1 >> s2 ;
    if ( s1.size() > s2.size() )    return cout << 0 , 0 ;
    fact1 [ 0 ] = 1 ;
    fact2 [ 0 ] = 1 ;

    for ( i = 1 ; i <= s2.size() ; ++ i )   {
        fact1 [ i ] = 1LL * fact1 [ i - 1 ] * 1000003 % MOD1 ;
        fact2 [ i ] = 1LL * fact2 [ i - 1 ] * 1000033 % MOD2 ;
    }
    for ( i = 0 ; i < s1.size() ; ++ i )    {
        hash1 = 1LL * ( hash1 + 1LL * fact1 [ i + 1 ] * ( s1 [ i ] ) % MOD1 ) % MOD1 ;
        hash2 = 1LL * ( hash2 + 1LL * fact2 [ i + 1 ] * ( s1 [ i ] ) % MOD2 ) % MOD2 ;
    }
    hash1 = 1LL * hash1 * fact1 [ s2.size() - s1.size() ] % MOD1 ;
    hash2 = 1LL * hash2 * fact2 [ s2.size() - s1.size() ] % MOD2 ;
    for ( i = 0 ; i < s1.size() ; ++ i )    {
        temp1 = 1LL * ( temp1 + 1LL * fact1 [ i + 1 ] * ( s2 [ i ] ) % MOD1 ) % MOD1 ;
        temp2 = 1LL * ( temp2 + 1LL * fact2 [ i + 1 ] * ( s2 [ i ] ) % MOD2 ) % MOD2 ;
    }
    temp10 = 1LL * temp1 * fact1 [ s2.size() - i ] % MOD1 ;
    temp20 = 1LL * temp2 * fact2 [ s2.size() - i ] % MOD2 ;
    if ( temp10 == hash1 && temp20 == hash2 )  {
        ++ cnt ;
        if ( cnt <= 1000 )
            sol.pb(i-s1.size()) ;
    }
    for ( ; i < s2.size() ; ++ i )  {
        temp1 = 1LL * ( temp1 + 1LL * fact1 [ i + 1 ] * ( s2 [ i ] ) % MOD1 ) % MOD1 ;
        temp2 = 1LL * ( temp2 + 1LL * fact2 [ i + 1 ] * ( s2 [ i ] ) % MOD2 ) % MOD2 ;
        temp1 = 1LL * ( temp1 - 1LL * fact1 [ i + 1 - s1.size() ] * ( s2 [ i - s1.size() ] ) % MOD1 + MOD1 ) % MOD1 ;
        temp2 = 1LL * ( temp2 - 1LL * fact2 [ i + 1 - s1.size() ] * ( s2 [ i - s1.size() ] ) % MOD2 + MOD2 ) % MOD2 ;
        temp10 = 1LL * temp1 * fact1 [ s2.size() - i - 1 ] % MOD1 ;
        temp20 = 1LL * temp2 * fact2 [ s2.size() - i - 1 ] % MOD2 ;
        if ( temp10 == hash1 && temp20 == hash2 )  {
            ++ cnt ;
            if ( cnt <= 1000 )
                sol.pb(i-s1.size()+1) ;
        }
    }
    out << cnt << '\n' ;
    for ( auto it : sol )   out << it << ' ' ;
    return 0 ;
}