Cod sursa(job #2930822)

Utilizator David8406Marian David David8406 Data 29 octombrie 2022 17:36:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
string a,b;
int nr;
pair<int,int> pw[1000005];
vector <int> v;
const int mod1=1e9+7,mod2=1e9+9;
void putere_74(){
    pw[0]={1,1};
    for (int i=1;i<=1000000;i++){
        pw[i].first=(1LL*74*pw[i-1].first)%mod1;
        pw[i].second=(1LL*74*pw[i-1].second)%mod2;
    }
}
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main(){
    fin>>a>>b;
    putere_74();
    pair<int,int> h,h2;
    for (int i=0;i<a.size();i++){
        h.first=(1LL*74*h.first+a[i]-'0')%mod1;
        h.second=(1LL*74*h.second+a[i]-'0')%mod2;
    }
    for (int i=0;i<a.size()-1;i++){
        h2.first=(1LL*74*h2.first+b[i]-'0')%mod1;
        h2.second=(1LL*74*h2.second+b[i]-'0')%mod2;
    }
    for (int i=a.size()-1;i<b.size();i++){
        h2.first=(1LL*74*h2.first+b[i]-'0')%mod1;
        h2.second=(1LL*74*h2.second+b[i]-'0')%mod2;
        if (h2==h){
            nr++;
            v.push_back(i-a.size()+1);
        }
        h2.first=(1LL*h2.first-((1LL*(b[i-a.size()+1]-'0')*pw[a.size()-1].first)%mod1)+mod1)%mod1;
        h2.second=(1LL*h2.second-((1LL*(b[i-a.size()+1]-'0')*pw[a.size()-1].second)%mod2)+mod2)%mod2;
    }
    fout<<nr<<"\n";
    for (int i=0;i<min(nr,1000);i++)
        fout<<v[i]<<" ";
}