Cod sursa(job #2978939)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 14 februarie 2023 17:33:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
const int mod1=999997;
const int mod2=1000003;
int ha1,ha2,nr,hb1,hb2;
vector<int>sol;
int main()
{
    f>>a>>b;
    int p1,p2,p;
    p1=p2=1;
    p=73;
    if(a.size()>b.size())
    {
        g<<0;
        return 0;
    }
    for(int i=0;i<a.size();i++)
    {
        ha1=(ha1*p+(int(a[i])))%mod1;
        ha2=(ha2*p+(int(a[i])))%mod2;

        hb1=(hb1*p+(int(b[i])))%mod1;
        hb2=(hb2*p+(int(b[i])))%mod2;
        if(i)
        {
            p1=(p*p1)%mod1;
            p2=(p*p2)%mod2;
        }
    }
    if(ha1==hb1&&ha2==hb2)
        sol.push_back(0),nr++;
    for(int i=a.size();i<b.size();i++)
    {
        int last=(int(b[i-a.size()]));
        int next=int(b[i]);
        hb1=((hb1-(last*p1)%mod1+mod1)*p+next)%mod1;
        hb2=((hb2-(last*p2)%mod2+mod2)*p+next)%mod2;
        if(ha1==hb1&&ha2==hb2)
            sol.push_back(i-a.size()+1),nr++;
    }
    g<<nr<<'\n';
    for(int i=0;i<min(nr,1000);i++)
        g<<sol[i]<<" ";
    return 0;
}