Cod sursa(job #3333032)

Utilizator informatica1210Alexia Petre informatica1210 Data 10 ianuarie 2026 15:52:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include "bits/stdc++.h"
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
long long mod,s[20002],poz[1002],pp[20002];
char a[20002],b[20002];
int main ()
{
    long long na,nb,p1,sa,x,nr,sb,c1;
    f>>a>>b;
    na=strlen(a);nb=strlen(b);
     p1=998244353;
    mod=1000000007;
    if (na>nb) g<<0;
    else
    {
        pp[0]=1;
        for (x=1;x<nb;x++)
        {
            pp[x]=(pp[x-1]*p1)%mod;
        }
        sa=0;
        for (x=0;x<na;x++)
        {
            sa=((sa*p1)%mod+(a[x]-'0'))%mod;
        }
        s[0]=b[0]-'0';
        for (x=1;x<nb;x++)
        {
            s[x]=((s[x-1]*p1)%mod+(b[x]-'0'))%mod;
        }
        nr=0;
        for (x=0;x+na-1<nb;x++)
        {
            if (x>0)
            {
                sb=(s[x+na-1]-(s[x-1]*pp[na])%mod+mod)%mod;
            }
            else sb=s[x+na-1];
            if (sb==sa) {nr++;if (nr<=1000) poz[nr]=x;}
        }
        g<<nr<<endl;
        c1=1000;
        for (x=1;x<=min(nr,c1);x++)
        {
            g<<poz[x]<<" ";
        }
    }
    f.close ();
    g.close ();
    return 0;
}