Cod sursa(job #3333341)

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