Pagini recente » Cod sursa (job #882299) | Rating Zuga Tudor (tudorzuga) | Cod sursa (job #3181779) | Cod sursa (job #3178865) | Cod sursa (job #1112922)
#include <fstream>
#include <string.h>
#define DIM 2000010
#define P 73
#define MOD1 100007
#define MOD2 100008
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[DIM], b[DIM], s[DIM];
int na, nb, ha1, ha2, p1, p2, hb1, hb2, i, nr;
int main(){
f.get(a, DIM);
f.get();
f.get(b, DIM);
f.get();
f.close();
na=strlen(a);
nb=strlen(b);
p1=p2=1;
ha1=ha2=0;
for(i=0; i<na; i++)
{
ha1=(ha1*P+a[i])%MOD1;
ha2=(ha2*P+a[i])%MOD2;
if (i!=0)
p1=(p1*P)%MOD1,
p2=(p2*P)%MOD2;
}
if(na>nb)
{
g<<"0\n";
return 0;
}
for(i=0; i<na; i++)
{
hb1=(hb1*P+b[i])%MOD1;
hb2=(hb2*P+b[i])%MOD2;
}
if(hb1==ha1 && hb2==ha2)
{
s[0]=1;
nr++;
}
for(i=na; i<nb; i++)
{
hb1=((hb1-(b[i-na]*p1)%MOD1+MOD1)*P+b[i])% MOD1;
hb2=((hb2-(b[i-na]*p2)%MOD2+MOD2)*P+b[i])% MOD2;
if(hb1==ha1 && hb2==ha2)
{
s[i-na+1]=1;
nr++;
}
}
g<<nr<<"\n";
nr=0;
for(i=0; i<nb && nr<1000; i++)
if(s[i])
{
nr++;
g<<i<<' ';
}
g<<"\n";
return 0;
}