Pagini recente » Cod sursa (job #1246848) | Cod sursa (job #1485047) | Cod sursa (job #1605360) | Cod sursa (job #463427) | Cod sursa (job #333114)
Cod sursa(job #333114)
#include<cstdio>
#include<string.h>
#define NMAX 2000001
#define MOD_1 666013
#define MOD_2 2000013
char sir[NMAX], pat[NMAX];
int N, M, PTHASH_1, PTHASH_2, FIRSTHASH_1, FIRSTHASH_2, pow255_1=1, pow255_2=1, matches, vec[1001];
inline int min(int a, int b)
{
if(a<b) return a;
return b;
}
void make_pat_hash() //face hashul patternului
{
for(int i=1; i<=M; i++)
{
PTHASH_1=PTHASH_1*255+pat[i];
PTHASH_1%=MOD_1;
PTHASH_2=PTHASH_2*255+pat[i];
PTHASH_2%=MOD_2;
FIRSTHASH_1=FIRSTHASH_1*255+sir[i];
FIRSTHASH_1%=MOD_1;
FIRSTHASH_2=FIRSTHASH_2*255+sir[i];
FIRSTHASH_2%=MOD_2;
}
if((FIRSTHASH_1==PTHASH_1)&&(FIRSTHASH_2==PTHASH_2))
{
matches++;
if(matches<=1000)
vec[matches]=1;
}
}
void make_hash(int x, int y, int &lasthash_1, int &lasthash_2)
{
lasthash_1-=(sir[x-1]*pow255_1)%MOD_1;
while(lasthash_1<0)
{
lasthash_1+=MOD_1;
}
lasthash_1=lasthash_1*255+sir[y];
lasthash_1%=MOD_1;
lasthash_2-=(sir[x-1]*pow255_2)%MOD_2;
while(lasthash_2<0)
{
lasthash_2+=MOD_2;
}
lasthash_2=lasthash_2*255+sir[y];
lasthash_2%=MOD_2;
if((lasthash_1==PTHASH_1)&&(lasthash_2==PTHASH_2))
{
matches++;
if(matches<=1000)
vec[matches]=x;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
//scanf("%s",&pat);
gets(pat);
M=strlen(pat);
//scanf("%s",&sir);
gets(sir);
N=strlen(sir);
for(int i = M; i ; --i) pat[i] = pat[i-1];
for(int i = N; i ; --i) sir[i] = sir[i-1];
int lasthash_1, lasthash_2;
for(int i=1;i<M;++i)
{
pow255_1*=255;
pow255_1%=MOD_1;
pow255_2*=255;
pow255_2%=MOD_2;
}
make_pat_hash();
lasthash_1=FIRSTHASH_1;
lasthash_2=FIRSTHASH_2;
for(int i=2; i<=N-M+1; i++)
{
make_hash(i,i+M-1,lasthash_1,lasthash_2);
}
printf("%d\n",matches);
for(int i=1; i<=min(matches, 1000); i++)
printf("%d ",vec[i]);
return 0;
}