Pagini recente » Cod sursa (job #1054361) | Cod sursa (job #438655) | Cod sursa (job #689518) | Cod sursa (job #2746264) | Cod sursa (job #2689517)
#include <fstream>
#include <cstdio>
#include <cstring>
#define MAXN 2000001
#define MOD1 100007
#define MOD2 100021
#define D 73
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
char pattern[MAXN], text[MAXN];
bool match[MAXN];
int m,n,nr,hashp1,hashp2,d1,d2,i;
int hasht1,hasht2;
void f()
{
n=strlen(pattern);
m=strlen(text);
d1=d2=1;
hashp1=hashp2=0;
for(i=0;i<n;++i)
{
hashp1=(hashp1*D+pattern[i])%MOD1;
hashp2=(hashp2*D+pattern[i])%MOD2;
if(i)
{
d1=(d1*D)%MOD1;
d2=(d2*D)%MOD2;
}
}
for (i=0;i<n;++i)
{
hasht1=(hasht1*D+text[i])%MOD1,
hasht2=(hasht2*D+text[i])%MOD2;
}
if(hasht1==hashp1&&hasht2==hashp2)
{
match[0]=true;
nr++;
}
for (i=n;i<m;++i)
{
hasht1=((hasht1-(text[i-n]*d1)%MOD1+MOD1)*D+text[i])%MOD1;
hasht2=((hasht2-(text[i-n]*d2)%MOD2+MOD2)*D+text[i])% MOD2;
if (hasht1==hashp1&&hasht2==hashp2)
{
match[i-n+1]=true;
nr++;
}
}
out<<nr<<'\n';
nr=0;
for (int i=0;nr<1000&&i<m;++i)
{
if(match[i])
{
out<<i<<" ";
nr++;
}
}
}
int main()
{
in>>pattern>>text;
if (n > m)
{
printf("0");
return 0;
}
f();
return 0;
}
//ajutor de la iulia