Cod sursa(job #2763079)

Utilizator KarinAAndrei Karina KarinA Data 11 iulie 2021 14:53:18
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

char a[2000005],b[2000005];
const int X1=37, X2=61;
const int MOD1=1000007, MOD2=666013;
vector <int> v;

void citeste()
{
    in>>a;
    in>>b;
}

void solve()
{
    int n=strlen(a),m=strlen(b);
    int hA1=0,hA2=0,hB1=0,hB2=0,p1=1,p2=1;
    for(int i=0;i<n;i++)
    {
        hA1 = (1LL*hA1 * X1 + a[i]) % MOD1;
        hA2 = (1LL*hA2 * X2 + a[i]) % MOD2;
    }
    if(n>m)
    {
        out<<0;
        return;
    }
    for(int i=0;i<n;i++)
    {
        hB1 = (1LL*hB1 * X1 + b[i]) % MOD1;
        hB2 = (1LL*hB2 * X2 + b[i]) % MOD2;
    }
    for(int i=1;i<=n-1;i++){
        p1=(p1*X1)%MOD1;
        p2=(p2*X2)%MOD2;
    }
    if(hB1==hA1 && hA2==hB2)
    {
        v.push_back(1);
    }
    for(int i=n;i<m;i++)
    {
        hB1 = ((hB1 - ((1LL*p1 * b[i-n]) % MOD1) + MOD1)*1LL * X1 + b[i]) % MOD1;
        hB2 = ((hB2 - ((1LL*p2 * b[i-n]) % MOD2) + MOD2)*1LL * X2 + b[i]) % MOD2;
        if(hB1==hA1 && hA2==hB2)
            v.push_back(i-n+1);
    }
    out<<v.size()<<'\n';
    for(int i=0;i<v.size() && i<1000;i++)
        out<<v[i]<<" ";
}

int main()
{
    citeste();
    solve();
    return 0;
}