Cod sursa(job #3300558)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 16 iunie 2025 23:57:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#define int long long

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int q1=1e9+7;
const int q2=666013;
const int B=263;
const int NMAX=2*1e6+5;

char p[NMAX], t[NMAX];
int ans[1005];

signed main()
{
    cin>>p;
    cin>>t;
    int i, hshp1=0, hshp2=0, pw1=1, pw2=1, hsht1=0, hsht2=0;
    for(i=0; p[i]; i++)
    {
        hshp1=(hshp1*B+p[i])%q1;
        hshp2=(hshp2*B+p[i])%q2;
        if(p[i+1])
        {
            pw1=(pw1*B)%q1;
            pw2=(pw2*B)%q2;
        }
        hsht1=(hsht1*B+t[i])%q1;
        hsht2=(hsht2*B+t[i])%q2;
    }
    int m=i, cnt=0;
    for(i=0; t[i+m-1]; i++)
    {
        if(hsht1==hshp1 && hsht2==hshp2)
        {
            cnt++;
            if(cnt<=1000) ans[cnt]=i;
        }
        hsht1=((hsht1+q1-(t[i]*pw1)%q1)*B+t[i+m])%q1;
        hsht2=((hsht2+q2-(t[i]*pw2)%q2)*B+t[i+m])%q2;
    }
    cout<<cnt<<'\n';
    for(i=1; i<=min(cnt, 1LL*1000); i++) cout<<ans[i]<<' ';
    return 0;
}