Cod sursa(job #2976469)

Utilizator MihaiCostacheCostache Mihai MihaiCostache Data 9 februarie 2023 11:14:43
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

#define MOD1 100021
#define MOD2 100007
#define B 73

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char match[2000001];
int hash11, hash12, nr, b1, b2;
int main()
{
    string s1, s2;
    fin>>s1>>s2;
    int n1=s1.size();
    int n2=s2.size();
    b1=b2=1;
    if(n1>n2)
    {
        cout<<"0";
        return 0;
    }
    for(int i=0; i<n1; i++)
    {
        hash11=(hash11*B+s1[i])%MOD1;
        hash12=(hash12*B+s1[i])%MOD2;
        if(i!=0)
        {
            b1=(b1*B)%MOD1;
            b2=(b2*B)%MOD2;
        }
    }
    int hash21=0;
    int hash22=0;
    for(int i=0; i<n1; i++)
    {
        hash21=(hash21*B+s2[i])%MOD1;
        hash22=(hash22*B+s2[i])%MOD2;
    }
    int nr=0;
    if(hash11==hash21 && hash12==hash22)
    {
        match[0]=1;
        nr++;
    }
    for(int i=n1; i<n2; i++)
    {
        hash21=((hash21-(s2[i-n1]*b1)%MOD1+MOD1)*B+s2[i])%MOD1;
        hash22=((hash22-(s2[i-n1]*b2)%MOD2+MOD2)*B+s2[i])%MOD2;
        if(hash11==hash21 && hash12==hash22)
        {
            match[i-n1+1]=1;
            nr++;
        }
    }
    fout<<nr<<"\n";
    nr=0;
    for(int i=0; i<n2 && nr<1000; i++)
    {
        if(match[i]>0)
        {
            nr++;
            fout<<i<<" ";
        }
    }
    fout<<"\n";
    return 0;
}