Cod sursa(job #2526104)

Utilizator andrei_044Andrei Constantin andrei_044 Data 18 ianuarie 2020 11:51:18
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a,b;

const long long N=999989977,A=699299929;
long long ha;
vector<int>v;
vector<long long>hb;
vector<long long>pA;

void hasha()
{
    for(auto c : a)
        ha=(ha*A+c)%N;
}

void hashb()
{
    hb.push_back(b[0]);
    for(int i=1;i<b.size();i++)
    {
        hb.push_back((hb[i-1]*A+b[i])%N);
    }
}

void powerA(int L)
{
    pA.push_back(1);
    for(int x=1;x<=L;x++)
    {
        pA.push_back((pA[x-1]*A)%N);
    }
}

long long getHash(int i,int j)
{
    if(i==0)
        return hb[j];
    i--;
    long long rez;
    rez=(hb[j]-(hb[i]*pA[j-i])%N+N)%N;
    return rez;
}

void sol()
{
    int nr=0;
    for(int i=0;i<b.size()-a.size();i++)
        if(getHash(i,i+a.size()-1)==ha)
        {
            nr++;
            v.push_back(i);
        }

    fout<<nr<<'\n';
    for(auto x : v)
    {
        fout<<x<<' ';
    }
}


int main()
{
    fin>>a>>b;
    hasha();
    hashb();
    powerA(b.size());
    sol();
    return 0;
}