Cod sursa(job #3333356)

Utilizator m.at.eiDabu Matei m.at.ei Data 13 ianuarie 2026 10:34:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
///strmatch
#include <bits/stdc++.h>;
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long sa,sb,s[1000001],pp[1000001];
int main()
{
    int  poz=0,nr=0,pot[1001],a[1000001],b[1000001],n,m,i,mod=998244353,p=1000000007;
    char a1[1000001],b1[1000001];
    f.getline(b1,1000001);
    f.getline(a1,1000001);
    m=strlen(b1);
    n=strlen(a1);
    for(i=0;i<n;i++)
       a[i+1]=a1[i];
    for(i=0;i<m;i++)
        b[i+1]=b1[i];
    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;
}