Cod sursa(job #3333240)

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

using namespace std;

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

int main()
{
    char a[2000001],b[2000001];
    int pp[200001],s[200001],x,p,mod,nr,poz[2001],sa,sb;
    p=1327;
    mod=10663;
    sa=sb=0;
    pp[0]=1;
    f.getline(b,20001);
    int m=strlen(b)-1;
    f.getline(a,20001);
    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++;
            poz[j]=x-1;
            nr++;
        }
    }
    g<<nr<<endl;
    for (int i=1;i<=j;i++)
        g<<poz[i]<<" ";
    return 0;
}