Cod sursa(job #3333250)

Utilizator carjila_raresCarjila Alexandru Rares carjila_rares Data 12 ianuarie 2026 15:04:06
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
///strmatch
#include <bits/stdc++.h>;
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{
    long long pot[1000],a[2000001],b[2000001],n,m,i,pp[2000001],mod=998244353,p=1000000007;
    char a1[2000001],b1[2000001];
    f.getline(b1,1000000);
    f.getline(a1,1000000);
    m=strlen(b1);
    n=strlen(a1);
    for(i=0;i<n;i++)
       a[i+1]=a1[i]-'A'+1;
    for(i=0;i<m;i++)
        b[i+1]=b1[i]-'A'+1;
    int poz=0,nr=0,sa,sb,s[1000];
    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;
}