Cod sursa(job #2976901)

Utilizator alessiamtr12Mitrica Alessia alessiamtr12 Data 10 februarie 2023 12:23:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include<vector>
#include<cstring>
#define BAZA 73
#define MOD1 100007
#define MOD2 104729
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000005],t[2000005];
int n,m,h1,h2,sol;
int v[2000005];
int main()
{
    fin>>s;
    fin>>t;
    n=strlen(s);
    m=strlen(t);
    if(n>m)
    {
        fout<<0;
        return 0;
    }
    int p1=1;
    int p2=1;
    int hs1=0;
    int hs2=0;
    for(int i=0;i<n;i++)
    {
        hs1=(hs1*BAZA+s[i])%MOD1;
        hs2=(hs2*BAZA+s[i])%MOD2;
        if(i!=0)
        {
            p1=(p1*BAZA)%MOD1;
            p2=(p2*BAZA)%MOD2;
        }
    }
    int ht1=0;
    int ht2=0;
    for(int i=0;i<n;i++)
    {
        ht1=(ht1*BAZA+t[i])%MOD1;
        ht2=(ht2*BAZA+t[i])%MOD2;
    }
    if(hs1==ht1&&hs2==ht2)
    {
        v[0]=1;
        sol++;
    }
    for(int i=n;i<m;i++)
    {
        ht1 = ((ht1 - (t[i - n] * p1) % MOD1 + MOD1) * BAZA + t[i]) % MOD1;
		ht2 = ((ht2 - (t[i - n] * p2) % MOD2 + MOD2) * BAZA + t[i]) % MOD2;

            if(hs1==ht1&&hs2==ht2)
            {
                v[i-n+1]=1;
                sol++;
            }

    }
    fout<<sol<<"\n";
    int k=0;
    for(int i=0;i<m &&k<1000;i++)
    {
        if(v[i])
        {
            fout<<i<<" ";
            k++;
        }
    }
    return 0;
}