Cod sursa(job #2361834)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 2 martie 2019 19:18:33
Problema Potrivirea sirurilor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
#define p 53

using namespace std;

const int m = 1e9+9 ;

ifstream fin ("strmatch.in") ;
ofstream fout("strmatch.out") ;

string sir1 , sir2 ;
vector<int> sol;

int main()
{
    int i ;
    long long curh , hs=0 ;
    fin >> sir1 ;
    fin >> sir2 ;
    if ( sir1.size() > sir2.size() )
    {
        fout << "0" ;
        return 0 ;
    }
    vector<long long> pp(sir2.size()) ;
    pp[0] = 1 ;
    for ( i = 1 ; i <= sir2.size()-1 ; i++ )
        pp[i] = ( pp[i-1] * p ) % m ;
    for ( i = 0 ; i <= sir1.size()-1 ; i++ )
    {
        if ( sir1[i] <= 'Z' )
            hs = ( hs + (sir1[i]-'A'+1) * pp[i] ) % m ;
        else
            hs = ( hs + (sir1[i]-'a'+27) * pp[i] ) % m ;
    }
    vector<long long> has(sir2.size(),0) ;
    for ( i = 0 ; i <= sir2.size()-1 ; i++ )
    {
        if ( sir2[i] <= 'Z' )
            has[i+1] = ( has[i] + (sir2[i]-'A'+1) * pp[i] ) % m ;
        else
            has[i+1] = ( has[i] + (sir2[i]-'a'+27)*pp[i] ) % m ;
    }
    for ( i = 0 ; i + sir1.size() - 1 < sir2.size() ; i++ )
    {
        curh = ( has[i+sir1.size()] + m - has[i] ) % m ;
        if ( curh == hs * pp[i] % m )
            sol.push_back(i) ;
    }
    fout << sol.size() << '\n' ;
    for ( auto ii : sol )
        fout << ii << " " ;
}