Pagini recente » Cod sursa (job #2740265) | Cod sursa (job #2344484) | Cod sursa (job #1700325) | Cod sursa (job #1185228) | Cod sursa (job #773846)
Cod sursa(job #773846)
#include <fstream>
#include <string.h>
#define MAX 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[MAX], b[MAX], s[MAX];
int na, nb, ha1, ha2, p1, p2, hb1, hb2, i, nr;
int main()
{
f.get(a, MAX);
f.get();
f.get(b, MAX);
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;
}