Pagini recente » Cod sursa (job #2430751) | Cod sursa (job #1462941) | Cod sursa (job #752787) | Cod sursa (job #2029461) | Cod sursa (job #629627)
Cod sursa(job #629627)
#include <cstdio>
#include <cstring>
#define baza 54
#define lmax 2000005
#define p1 666013
using namespace std;
long nra[3], nrb[3], k, i, la, lb, rez, blan[3], x, vrez[1005], p;
bool ok, eg;
char a[lmax], b[lmax];
long num(char q)
{
if ((q>='a')&&(q<='z'))
return q-'a';
if ((q>='A')&&(q<='Z'))
return q-'A'+27;
return q-'0'+54;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(b); gets(a);
la=strlen(a); lb=strlen(b);
blan[0]=1; blan[1]=1;
for (p=666013;p<=666014;p++)
{
for (i=1;i<=lb-1;i++)
blan[p-p1]=(blan[p-p1]*baza)%p;
for (i=0;i<lb;i++)
{
nra[p-p1]=(nra[p-p1]*baza+num(a[i]))%p;
nrb[p-p1]=(nrb[p-p1]*baza+num(b[i]))%p;
}
}
i=0;
if ((nra[1]==nrb[1])&&(nra[0]==nrb[0]))
vrez[++rez]=0;
for (i=1;i<=la-lb;i++)
{
eg=1;
for (p=666013;p<=666014;p++)
{
nra[p-p1]=(nra[p-p1]-blan[p-p1]*num(a[i-1]))%p;
nra[p-p1]=(nra[p-p1]*baza)%p;
nra[p-p1]+=num(a[i+lb-1]);
nra[p-p1]=(nra[p-p1]+p)%p;
if (nra[p-p1]!=nrb[p-p1])
eg=0;
}
rez+=eg;
if ((rez<=1000) &&(eg))
vrez[rez]=i;
}
printf("%ld\n",rez);
if (rez>1000)
rez=1000;
for (i=1;i<=rez;i++)
printf("%ld ",vrez[i]);
return 0;
}