Cod sursa(job #3370248)

Utilizator informatica1210Alexia Petre informatica1210 Data 24 octombrie 2026 18:25:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include "bits/stdc++.h"
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
long long mod,s[2000002];
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,p;
    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;
    p=put(ba,n1-1);
    for (x=0;x<n2-n1+1;x++)
    {
        y=x+n1-1;
        if (x!=0) s3=((s3-((b[x-1]-'0')*p)%mod+mod)*ba+(b[y]-'0')+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;
}