Pagini recente » Cod sursa (job #2903115) | Cod sursa (job #2903113) | Cod sursa (job #781227) | Cod sursa (job #3180762) | Cod sursa (job #2533806)
#include <fstream>
#include <vector>
#define A 911382323
#define B 972663749
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const long long lim=2e6+3;
vector<long long> sol;
int main()
{
string a,b;
long long na,nb,ha=0,hb=0,cnt=0,p=1;
cin>>a>>b;
na=a.size(),nb=b.size();
if(na>nb)
{
cout<<0;
return 0;
}
for(long long i=0;i<na;++i)
{
ha=(ha*A+a[i]-48)%B;
hb=(hb*A+b[i]-48)%B;
p=(p*A)%B;
}
if(ha==hb)
{
++cnt;
sol.push_back(0);
}
for(long long i=na;i<nb;++i)
{
hb=(hb*A+b[i]-48)%B;
hb=(hb+B-(p*(b[i-na]-48))%B)%B;
if(ha==hb)
{
++cnt;
if(cnt<=1000)
sol.push_back(i-na+1);
}
}
cout<<cnt<<'\n';
long long nr=sol.size();
for(long long i=0;i<nr;++i)
cout<<sol[i]<<' ';
return 0;
}