Cod sursa(job #3333208)

Utilizator DasapSapunaru Daniel Dasap Data 12 ianuarie 2026 00:06:25
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 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,MOD=1e9+7;
int pow(int a,int b){
    int rez=1;
    while(b){
        if(b&1)rez=1ll*rez*a%MOD;
        a=1ll*a*a%MOD;
        b/=2;
    }
    return rez;
}
int n,m,hashA,p1=1,baza=53,hashB,p2=1,inv,i;
string a,b;
vector<int>v;
int main()
{
    fin>>a>>b;
    inv=pow(baza,MOD-2);
    for(i=0;i<a.size();i++){
        hashA=(hashA+1ll*a[i]*p1)%MOD;
        p1=1ll*p1*baza%MOD;
    }
    for(i=0;i<b.size();i++){
        if(i<a.size()){
            hashB=(hashB+1l*b[i]*p2)%MOD;
            p2=1ll*p2*baza%MOD;
        }
        else{
            hashB=(hashB-b[i-a.size()]+1ll*b[i]*p2+MOD)*inv%MOD;
        }
        if(hashA==hashB)v.push_back(i-a.size()+1);
    }
    fout<<v.size();
    for(i=0;i<min(int(v.size()),1000);i++)fout<<v[i]<<' ';
    return 0;
}