Cod sursa(job #2370524)

Utilizator HaesteinnSabau Florin Vlad Haesteinn Data 6 martie 2019 12:31:43
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
typedef long long ll;
const ll MOD1=1000000007;
const ll MOD2=994366432;
const ll P1=997898399;
const ll P2=859925329;

string a,b;
ll hashA1,hashA2,hashB1,hashB2;
ll p1,p2;

void precalculate()
{
    p1=1;
    p2=1;
    for(int i=0;i<a.length();i++)
    {
        p1=(p1*P1)%MOD1;
        p2=(p2*P2)%MOD2;
        hashA1=(hashA1*P1+a[i])%MOD1;
        hashA2=(hashA2*P2+a[i])%MOD2;
        hashB1=(hashB1*P1+b[i])%MOD1;
        hashB2=(hashB2*P2+b[i])%MOD2;
    }
}

int nr;

int main()
{
    fin>>a>>b;
    vector<int> poz;
    int aL=a.length();
    int bL=b.length();
    if(aL>bL)
    {
        fout<<"0\n";
        return 0;
    }
    precalculate();
//    fout<<hashish<<" "<<hashing(5,7);
    for(int i=0;i<=bL-aL;i++)
    {
        if(hashA1==hashB1&&hashA2==hashB2)
        {
            poz.push_back(i);
            nr++;
        }
        hashB1=(hashB1*P1+b[i+aL]-(b[i]*p1)%MOD1)%MOD1;
        hashB2=(hashB2*P2+b[i+aL]-(b[i]*p2)%MOD2)%MOD2;
    }
    fout<<nr<<'\n';
    for(int i=0;i<min(poz.size(),1000);i++)
    {
        fout<<poz[i]<<' ';
    }
    return 0;
}