Cod sursa(job #3333203)

Utilizator DasapSapunaru Daniel Dasap Data 11 ianuarie 2026 23:09:47
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include<fstream>
#define ll long long
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");const ll NMAX=2e6+5,MOD=1e9+7;
ll dp[NMAX],baza=53,p[NMAX],n,val,valacm,k,temp,i;
vector<int>afis;
string a,b;
int main()
{
    fin>>a>>b;
    k=a.size();
    n=max(a.size(),b.size());
    p[0]=1;
    for(i=1;i<=n;i++)p[i]=p[i-1]*baza%MOD;
    for(i=0;i<a.size();i++){
        val=(val+a[i]*p[i])%MOD;
    }
    dp[0]=b[0]*p[0]%MOD;
    for(i=1;i<b.size();i++){
        dp[i]=(dp[i-1]+b[i]*p[i])%MOD;
    }
    for(i=a.size()-1;i<b.size();i++){
        if(i==a.size()-1)valacm=dp[i];
        else valacm=(dp[i]-dp[i-k]+MOD)%MOD;
        temp=(val*p[i-(a.size()-1)])%MOD;
        if(temp==valacm)afis.push_back(i-k+1);
    }
    fout<<afis.size()<<'\n';
    k=min(int(afis.size()),1000);
    for(i=0;i<k;i++)fout<<afis[i]<<' ';
    return 0;
}