Pagini recente » Cod sursa (job #2200004) | Cod sursa (job #1887006) | Cod sursa (job #2709359) | Cod sursa (job #1564857) | Cod sursa (job #2976482)
#include <fstream>
#include <cstring>
#define mod 100007
#define mod1 100021
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
long long n,m,i,pp1,haa,hbb,pp,ha,hb,nr,l[2000001];
char a[2000001],b[2000001];
int main()
{
fin>>a+1;
fin>>b+1;
n=strlen (a+1);
m=strlen (b+1);
if (n>m)
{
fout<<"0";
return 0;
}
pp=1;
pp1=1;
ha=0;
haa=0;
for (i=1; i<=n; i++)
{
ha=(ha*26+a[i])%mod;
haa=(haa*26+a[i])%mod1;
if (i>1)
{
pp=(pp*26)%mod;
pp1=(pp1*26)%mod1;
}
}
hb=0;
hbb=0;
for (i=1; i<=n; i++)
{
hb=(hb*26+b[i])%mod;
hbb=(hbb*26+b[i])%mod1;
}
if (ha==hb&&haa==hbb)
l[++nr]=1;
for (i=n+1; i<=m; i++)
{
hb=((hb-(b[i-n]*pp)%mod+mod)*26+b[i])%mod;
hbb=((hbb-(b[i-n]*pp1)%mod1+mod1)*26+b[i])%mod1;
if (ha==hb&&haa==hbb)
l[++nr]=i-n+1;
}
fout<<nr<<"\n";
for (i=1; i<=min (nr,1ll*1000); i++)
fout<<l[i]-1<<" ";
return 0;
}