Cod sursa(job #2361930)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 2 martie 2019 20:27:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 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 ;
    long long curh , hs=0 ;
    fin >> sir1 ;
    fin >> sir2 ;
    if ( sir1.size() > sir2.size() )
    {
        fout << "0" ;
        return 0 ;
    }
    vector<int> pp(sir2.size()+2) ;
    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' && 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<int> has(sir2.size()+2,0) ;
    for ( i = 0 ; i <= sir2.size()-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 ;
    }
    for ( i = 0 ; i + sir1.size() - 1 < sir2.size() ; i++ )
        curh = ( has[i+sir1.size()] + 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] << " " ;
}