Cod sursa(job #2807594)

Utilizator Matei_PanzariuMatei Panzariu Matei_Panzariu Data 23 noiembrie 2021 23:00:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<cstring>
#define mod1 100003
#define mod2 100007
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
long long ha1,ha2,na,nb,h1,h2,v[2000001],k,p1=1,p2=1;
char A[2000001],B[2000001];
int c(char ch)
{
    return ch;
}
int main()
{
    cin>>A;
    cin>>B;
    na=strlen(A);
    nb=strlen(B);
    for(int i=0; i<na; i++)
    {
        ha1=(ha1*73+c(A[i]))%mod1;
        ha2=(ha2*73+c(A[i]))%mod2;
    }
    for(int i=0; i<na; i++)
    {
        h1=(h1*73+c(B[i]))%mod1;
        h2=(h2*73+c(B[i]))%mod2;
        if(i)
        {
            p1=(p1*73)%mod1;
            p2=(p2*73)%mod2;
        }
    }
    //p1/=126;
    //p2/=126;
    if(h1==ha1 && h2==ha2)
        v[++k]=0;
    for(int i=na; i<nb; i++)
    {
        h1=((h1-(c(B[i-na])*p1)%mod1+mod1)*73+c(B[i]))%mod1;
        h2=((h2-(c(B[i-na])*p2)%mod2+mod2)*73+c(B[i]))%mod2;
        if(ha1==h1 && ha2==h2)
            v[++k]=i-na+1;
    }
    cout<<k<<'\n';
    if(k>1000)
        k=1000;
    for(int i=1; i<=k; i++)
        cout<<v[i]<<' ';
}