Cod sursa(job #2361940)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 2 martie 2019 20:32:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
#define p 67

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 , SA , SB ;
    long long curh , hs=0 ;
    fin >> sir1 ;
    fin >> sir2 ;
    SA = sir1.size() ;
    SB = sir2.size() ;
    if ( SA > SB )
    {
        fout << "0" ;
        return 0 ;
    }
    vector<long long> pp(SB+2) ;
    pp[0] = 1 ;
    for ( i = 1 ; i <= SB-1 ; i++ )
        pp[i] = ( pp[i-1] * p ) % m ;
    for ( i = 0 ; i <= SA-1 ; i++ )
    {
        if ( sir1[i] <= 'Z' && sir1[i] >= 'A' )
            hs = ( hs + (sir1[i]-'A'+1) * pp[i] ) % m ;
        else if ( sir1[i] <= 'z' && sir1[i] >= 'a' )
            hs = ( hs + (sir1[i]-'a'+27) * pp[i] ) % m ;
        else
            hs = ( hs + (sir1[i]-'0'+53) * pp[i] ) % m ;
    }
    vector<long long> has(SB+2,0) ;
    for ( i = 0 ; i <= SB-1 ; i++ )
    {
        if ( sir2[i] <= 'Z' && sir2[i] >='A' )
            has[i+1] = ( has[i] + (sir2[i]-'A'+1) * pp[i] ) % m ;
        else if ( sir2[i] <= 'z' && sir2[i] >= 'a' )
            has[i+1] = ( has[i] + (sir2[i]-'a'+27) *pp[i] ) % m ;
        else
            has[i+1] = ( has[i] + (sir2[i]-'0'+53) *pp[i] ) % m ;
    }
    sir1.clear() ;
    sir2.clear() ;
    for ( i = 0 ; i + SA - 1 < SB ; i++ )
        curh = ( has[i+SA] + m - has[i] ) % m ;
        if ( curh == (1LL*hs * pp[i]) % m )
            sol.push_back(i) ;
    int ct = sol.size() ;
    fout << ct << '\n' ;
    for ( int ii = 0 ; ii < min(1000,ct) ; ii++ )
        fout << sol[ii] << " " ;
}