Cod sursa(job #3153661)

Utilizator DariusM17Murgoci Darius DariusM17 Data 30 septembrie 2023 16:16:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
#define ll long long
const int MOD1=666013,MOD2=10027,baza=73 ;
string a,b ;
ll hashA1,hashA2,aux1=1,aux2=1,h1,h2 ;
vector <int> ans ;
int main()
{
    fin>>a>>b ;
    ll aux1 = 1, aux2 = 1;
    for (int i = 0; i < a.size(); ++i)
    {
        hashA1 = (hashA1 * baza + a[i]) % MOD1;
        hashA2 = (hashA2 * baza + a[i]) % MOD2;
        if (i != 0) aux1 = (aux1 * baza) % MOD1, aux2 = (aux2 * baza) % MOD2;
    }
    ll p1 = 0, p2 = 0;
    for (int i = 0; i < a.size(); ++i)
    {
        p1 = (p1 * baza + b[i]) % MOD1;
        p2 = (p2 * baza + b[i]) % MOD2;
    }
    if (p1 == hashA1 && p2 == hashA2) ans.push_back(0);
    for (int i = a.size(); i < b.size(); ++i)
    {
        p1 = ((((p1 - aux1 * b[i - a.size()]) % MOD1) + MOD1) * baza + b[i]) % MOD1;
        p2 = ((((p2 - aux2 * b[i - a.size()]) % MOD2) + MOD2) * baza + b[i]) % MOD2;
        if (hashA1 == p1 && hashA2 == p2) ans.push_back(i - a.size() + 1);
    }
    fout<<ans.size()<<'\n' ;
    for(int i=0; i<min(1000,(int)ans.size()); ++i) fout<<ans[i]<<" ";
    return 0;
}