Cod sursa(job #3333390)

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

using namespace std;

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

long long pp[2000001],s[2000001],sa,sb;

int main()
{
    char a[2000001],b[2000001];
    int p,poz[1001],mod,x;
    p=998244353;
    mod=1000000007;
    sa=sb=0;
    pp[0]=1;
    f.getline(b,2000001);
    int m=strlen(b);
    f.getline(a,2000001);
    int n=strlen(a);
    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-1]-'0')%mod;
    }
    sb=b[1];
    for(x=2; x<=m; x++)
    {
        sb=(sb*p+b[x-1]-'0')%mod;
    }
    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<=min(j,1000); i++)
        g<<poz[i]<<" ";
    return 0;
}