Pagini recente » Cod sursa (job #717000) | Cod sursa (job #1445088) | Cod sursa (job #649319) | Cod sursa (job #931916) | Cod sursa (job #1969208)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define nmax 2000010
#define p 101
#define mod1 107
#define mod2 103
char a[nmax],b[nmax];
int Ahash1,Ahash2,Bhash1,Bhash2,poz[1002],cate,pmax1,pmax2;
int main()
{
int nra,nrb,i;
f>>a;
f>>b;
nra=strlen(a)-1;
pmax1=pmax2=1;
for(i=0;i<=nra;i++)
{
Ahash1=(Ahash1*p+a[i])%mod1;
Ahash2=(Ahash2*p+a[i])%mod2;
if(i)
{pmax1*=p;
pmax1%=mod1;
pmax2*=p;
pmax2%=mod2;}
}
nrb=strlen(b)-1;
if(nrb<nra)
g<<"0";
else
{
for(i=0;i<=nra;i++)
{
Bhash1=(Bhash1*p+b[i])%mod1;
Bhash2=(Bhash2*p+b[i])%mod2;
}
if(Bhash1==Ahash1 and Bhash2==Ahash2)
{
cate+=1;
poz[cate]=0;
}
int ok=0;
for(i=nra+1;i<=nrb;i++)
{
if(i==7)
ok=1;
Bhash1-=(pmax1*(b[i-nra-1]))%mod1;
if(Bhash1<0)
Bhash1+=mod1;
Bhash1=(Bhash1*p+b[i])%mod1;
Bhash2-=(pmax2*(b[i-nra-1]))%mod2;
if(Bhash2<0)
Bhash2+=mod2;
Bhash2=(Bhash2*p+b[i])%mod2;
if(Bhash1==Ahash1 and Bhash2==Ahash2)
{
cate+=1;
if(cate<=1000)
poz[cate]=i-nra;
}
}
g<<cate<<'\n';
cate=min(cate,1000);
for(i=1;i<=cate;i++)
g<<poz[i]<<" ";
}
return 0;
}