Cod sursa(job #3333385)

Utilizator m.at.eiDabu Matei m.at.ei Data 13 ianuarie 2026 10:52:17
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
///strmatch
#include <bits/stdc++.h>;
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int sa,sb,s[2000001],pp[2000001];
int main()
{
    int  poz=0,nr=0,pot[1001],a[2000001],b[2000001],n,m,i,mod=90001,p=49991;
    char a1[2000001],b1[2000001];
    f.getline(b1,2000001);
    f.getline(a1,2000001);
    m=strlen(b1);
    n=strlen(a1);
    for(i=0;i<n;i++)
       a[i+1]=a1[i]-'0';
    for(i=0;i<m;i++)
        b[i+1]=b1[i]-'0';
    pp[0]=1;
    for(i=1;i<=m;i++)
        pp[i]=(pp[i-1]*p)%mod;
    sb=b[1];
    for(i=2;i<=m;i++)
        sb=(sb*p+b[i])%mod;
    s[1]=a[1];
    for(i=2;i<=n;i++)
        s[i]=(s[i-1]*p+a[i])%mod;
    for(i=1;i<=n-m+1;i++)
    {
        sa=(s[i+m-1]-(s[i-1]*pp[m])%mod+mod)%mod;
        if(sa==sb)
        {
            nr++;
            if(nr<1001)
                pot[nr]=i;
        }
    }
    g<<nr<<endl;
    for(i=1;i<=min(nr,1000);i++)
        g<<pot[i]-1<<" ";
    f.close();
    g.close();
    return 0;
}