Pagini recente » Cod sursa (job #2677392) | Cod sursa (job #2947957) | Cod sursa (job #3305454) | Cod sursa (job #3352051) | Cod sursa (job #3339789)
//
// 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=1000000013;
int val(char x)
{
return (int)x;
}
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*130%mod+(int)a[i])%mod;
}
int n=a.size();
long long hashb=0;
for(int i=0;i<n;i++)
{
hashb=(hashb*130%mod+(int)b[i])%mod;
}
int nr=0;
vector<int>ans;
long long put=pow(130,n-1);
put%=mod;
if(hasha==hashb){nr++;ans.push_back(0);}
for(int i=n;i<b.size();i++)
{
hashb=hashb-(int)b[i]*put;
hashb%=mod;
if(hashb<0)hashb+=mod;
hashb=(hashb*130%mod+(int)b[i])%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;
}