Pagini recente » Cod sursa (job #2365091) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #1069622) | Cod sursa (job #790738) | Cod sursa (job #2711214)
#include <iostream>
#include <fstream>
#include <cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
char a[2000001], b[2000001];
int d=72, potriv[2000001], nr; //10 cif, 26 litere
int main()
{
f.getline(a, 2000001);
f.getline(b, 2000001);
int lg1=strlen(a), lg2=strlen(b);
if(lg1>lg2)
{g<<0; return 0;}
int hasha1=a[0], hasha2=a[0], hashb1=b[0], hashb2=b[0], put1=1, put2=1;
for(int i=1; i<lg1; i++)
{
hasha1=(hasha1*d+a[i])%MOD1;
hasha2=(hasha2*d+a[i])%MOD2;
hashb1=(hashb1*d+b[i])%MOD1;
hashb2=(hashb2*d+b[i])%MOD2;
put1=(put1*d)%MOD1;
put2=(put2*d)%MOD2;
}
if(hasha1==hashb1&&hasha2==hashb2)
{
potriv[0]=1;
nr++;
}
for(int i=lg1; i<lg2; i++)
{
hashb1=((hashb1-(b[i-lg1]*put1)%MOD1+MOD1)*d+b[i])%MOD1;
hashb2=((hashb2-(b[i-lg1]*put2)%MOD2+MOD2)*d+b[i])%MOD2;
if(hasha1==hashb1&&hasha2==hashb2)
{
potriv[i-lg1+1]=1;
nr++;
}
}
g<<nr<<'\n';
nr=0;
for(int i=0;i<lg2&&nr<1000;i++)
if(potriv[i]==1)
{
g<<i<<' ';
nr++;
}
return 0;
}