Cod sursa(job #3333248)

Utilizator badicabadelClaudiu Ioan Badica badicabadel Data 12 ianuarie 2026 14:54:19
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int main()
{
    char a[2000001],b[2000001];
    long long pp[2000001],s[2000001],x,p,mod,nr,poz[1001],sa,sb;
    p=998244353;
    mod=1000000007;
    sa=sb=0;
    pp[0]=1;
    f.getline(b,2000001);
    int m=strlen(b)-1;
    f.getline(a,2000001);
    int n=strlen(a)-1;
    for(x=1; x<=m; x++)
    {
        pp[x]=(pp[x-1]*p)%mod;
    }
    s[1]=a[1];
    for(x=2; x<=n; x++)
    {
        s[x]=(s[x-1]*p+a[x])%mod;
    }
    sb=b[1];
    for(x=2; x<=m; x++)
    {
        sb=(sb*p+b[x])%mod;
    }
    nr=0;
    int j=0;
    for(x=1; x<=n-m+1; x++)
    {
        sa=(s[x+m-1]-(s[x-1]*pp[m])%mod+mod)%mod;
        if(sa==sb)
        {
            j++;
            if (j<=1000)
            {
                poz[j]=x-1;
            }
        }
    }
    g<<j<<endl;
    for (int i=1; i<=j; i++)
        g<<poz[i]<<" ";
    return 0;
}