Cod sursa(job #3338665)

Utilizator Andrada_MincaAndrada Minca Andrada_Minca Data 4 februarie 2026 13:18:32
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
//
//  main.cpp
//  Potrivirea sirurilor cu hash
//
//  Created by Andrada Minca on 04.02.2026.
//

#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int mod=1000000009;
int main()
{
    string a,b;
    cin>>a>>b;
    //facem hash a
    long long hasha=0;
    for(int i=0;i<a.size();i++)
    {
        hasha=(hasha*26%mod+(int(a[i])-'a'))%mod;
    }
    int n=a.size();
    long long hashb=0;
    for(int i=0;i<n;i++)
    {
        hashb=(hashb*26%mod+(int(b[i])-'a'))%mod;
    }
    int nr=0;
    vector<int>ans;
    long long put=pow(26,n-1);
    if(hasha==hashb){nr++;ans.push_back(0);}
    for(int i=n;i<b.size();i++)
    {
        hashb=hashb-(int(b[i-n])-'a')*put;
        hashb%=mod;
        hashb=(hashb*26%mod+(int(b[i])-'a'))%mod;
        if(hasha==hashb){nr++;ans.push_back(i-n+1);}
    }
    cout<<nr<<'\n';
    for(int i=0;i<min(1000,nr);i++)cout<<ans[i]<<" ";
    return 0;
}