Cod sursa(job #3370246)

Utilizator informatica1210Alexia Petre informatica1210 Data 24 octombrie 2026 18:18:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include "bits/stdc++.h"
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
long long mod,s[20002];
vector<long long> v;
long long put (long long b,long long p)
{
    if (p==0) return 1;
    if (p==1) return b;
    if (p%2==0) return put((b*b)%mod,p/2)%mod;
    if (p%2==1) return (b*put((b*b)%mod,p/2)%mod)%mod;
}
int main ()
{
    long long ba,x,s1,nr,s3,y,n1,n2;
    string a,b;
    mod=1000000007;
    ba=256;
    f>>a>>b;
    n1=a.size();
    n2=b.size();
    s1=0;
    s1=a[0]-'0';
    for (x=1;x<n1;x++)
    {
        s1=((1LL*s1*ba)%mod+(a[x]-'0'))%mod;
    }
    s[0]=b[0]-'0';
    for (x=1;x<n2;x++)
    {
        s[x]=((s[x-1]*ba)%mod+(b[x]-'0'))%mod;
    }
    nr=0;
    for (x=0;x<n2-n1+1;x++)
    {
        y=x+n1-1;
        if (x!=0) s3=(s[y]-(s[x-1]*put(ba,n1))%mod+mod)%mod;
        else s3=s[y];
        if (s3==s1)
        {
            nr++;
            if (nr<=1000) v.push_back(x);
        }
    }
    g<<nr<<endl;
    for (auto x : v)
        g<<x<<" ";
    f.close ();
    g.close ();
    return 0;
}