Cod sursa(job #2457983)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 19 septembrie 2019 11:12:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string s1,s2;
vector<int >a;
long long nr160,nr10,nr260,nr210;
const long  long mod1=10e9+7,mod2=666013;

int main()
{
    int put73=1;
    cin>>s1>>s2;
    for(int i=1;i<s1.size();i++){
        put73*=73;
    }
    for(int i=0;i<s1.size();i++){
        nr160=((long long)nr160*73+(s1[i]-'0'+1))%mod2;
        nr10=((long long)nr10*73+(s1[i]-'0'+1))%mod1;
    }
    for(int i=0;i<s1.size();i++){
        nr260=((long long)nr260*73+(s2[i]-'0'+1))%mod2;
        nr210=((long long)nr210*73+(s2[i]-'0'+1))%mod1;
    }
    if((nr160==nr260) && (nr10==nr210))
        a.push_back(0);
    for(int i=s1.size();i<s2.size();i++){
        nr260=(((long long)nr260-(s2[i-s1.size()]-'0'+1)*put73)*73+(s2[i]-'0'+1))%mod2 + mod2;
        nr260%=mod2;
        nr210=(((long long)nr210-(s2[i-s1.size()]-'0'+1)*put73)*73+(s2[i]-'0'+1))%mod1 + mod1;
        nr210%=mod1;
        if((nr10==nr210) && (nr160==nr260))
            a.push_back(i-s1.size()+1);
    }
    cout<<a.size()<<'\n';
    for(int i=0;i<min(1000,(int)a.size());i++)
                cout<<a[i]<<" ";
    return 0;
}