Pagini recente » Cod sursa (job #1763959) | Cod sursa (job #935114) | Cod sursa (job #1262022) | Cod sursa (job #1448019) | Cod sursa (job #2589739)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD=1023317;
const int baza=29;
const int nmax=2000005;
string n,m;
int nrN,nrM,base[nmax];
long long hashN,hashM,hashS[nmax];
void read()
{
fin>>n>>m;
nrN=n.length();
nrM=m.length();
}
void basePow()
{
base[0]=1;
for(int i=1;i<=nrN;i++)
base[i]=(base[i-1]*baza)%MOD;
}
void solve()
{
basePow();
for(int i=0;i<nrN;i++)
{
hashN=(1LL*hashN*baza+n[i])%MOD;
hashM=(1LL*hashM*baza+m[i])%MOD;
}
hashS[nrN-1]=hashM;
for(int i=nrN;i<nrM;i++)
{
hashS[i]=(1LL*hashS[i-1]*baza+m[i])%MOD;
hashS[i]=1LL*hashS[i]-((1LL*m[i-nrN]*base[nrN])%MOD);
}
int ans=0;
for(int i=nrN-1;i<nrM;i++)
if(hashS[i]==hashN)ans++;
fout<<ans<<"\n";
for(int i=nrN-1;i<nrM;i++)
{
if(hashS[i]==hashN)
if(i-nrN+1<=1000)
fout<<i-nrN+1<<" ";
}
}
int main()
{
read();
solve();
return 0;
}