Cod sursa(job #3333581)

Utilizator RZV139fjDragomir Ioan Razvan RZV139fj Data 14 ianuarie 2026 12:32:48
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long mod=1e9+7;
int base=31;
long long h=0;
char smic[2000000];
char smare[2000000];
long long H=0;
long long hash1=0;
long long v[2000000];

int cnt=0;

int main()
{
    fin.getline(smic,2000000);
    fin.getline(smare,2000000);

    for(int i=0;i<strlen(smic);i++)
    {
        H=(H*base+(smic[i]))%mod;
    }

    int NMIC=strlen(smic);
    int power=1;
    for(int i=0;i<NMIC;i++)
    {
        hash1=(hash1*base+smare[i])%mod;
        if(i!=0)
        {
            power=(power*base)%mod;
        }
    }
    if(hash1==H)
    {
        bool ok=true;
        for(int j=0;j<NMIC;j++)
        {
            if(smic[j]!=smare[j]) ok=false;
        }
        if(ok==true)
        {
            v[cnt++]=0;
        }
    }

    for(int i=NMIC;smare[i]!='\0';i++)
    {
        hash1=(((hash1-((smare[i-NMIC])*power)%mod)*base+mod)%mod+smare[i])%mod;
        if(hash1==H)
        {
            bool ok=true;
            for(int j=0;j<NMIC;j++)
            {
                if(smic[j]!=smare[j+i-NMIC+1]) ok=false;
            }
            if(ok==true)
            {
                v[cnt]=i-NMIC+1;
                cnt++;
            }
        }
    }
    fout<<cnt<<'\n';
    for(int i = 0; i < min(cnt, 1000); i++)
        fout << v[i] << " ";

    return 0;
}