Pagini recente » Cod sursa (job #893591) | Cod sursa (job #753206) | Cod sursa (job #2472940) | Cod sursa (job #537840) | Cod sursa (job #2589743)
#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;
int hashN,hashM,hashS[nmax],base[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=(hashN*baza+n[i])%MOD;
hashM=(hashM*baza+m[i])%MOD;
}
hashS[nrN-1]=hashM;
for(int i=nrN;i<nrM;i++)
{
hashS[i]=(hashS[i-1]*baza+m[i])%MOD;
hashS[i]=hashS[i]-((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<=1000)
fout<<i-nrN+1<<" ";
}
}
int main()
{
read();
solve();
return 0;
}