Cod sursa(job #3333201)

Utilizator DasapSapunaru Daniel Dasap Data 11 ianuarie 2026 23:04:04
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 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 int NMAX=2e6+5;
ll dp[NMAX],baza=60,p[NMAX],n,val,valacm,k,temp,i;const int MOD=1e9+7;
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]-'A'+1)*p[i])%MOD;
    }
    dp[0]=(b[0]-'a'+1)*p[0]%MOD;
    for(i=1;i<b.size();i++){
        dp[i]=(dp[i-1]+(b[i]-'A'+1)*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()),999);
    for(i=0;i<k;i++)fout<<afis[i]<<' ';
    return 0;
}