Pagini recente » Cod sursa (job #2890223) | Cod sursa (job #1612641) | Cod sursa (job #685156) | Cod sursa (job #1170122) | Cod sursa (job #1677183)
#include<fstream>
#include<string.h>
using namespace std;
int p=73;
int MOD1=100007;
int MOD2=100021;
char a[2000002],b[20000002],match[2000002];
int n1,n2,hasha1,hasha2,p1,p2,hashb1,hashb2,nr,i;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.get(a,2000002,'\n');
fin.get();
fin.get(b,2000002,'\n');
fin.get();
n1=strlen(a);
n2=strlen(b);
p1=1;
p2=1;
hasha1=0;
hasha2=0;
for(i=0;i<n1;i++)
{
hasha1 = (hasha1 * p + a[i]) % MOD1;
hasha2 = (hasha2 * p + a[i]) % MOD2;
if (i != 0)
{
p1 = (p1 * p) % MOD1,
p2 = (p2 * p) % MOD2;
}
}
if (n1 > n2)
{
fout<<"0";
return 0;
}
hashb1=0;
hashb2=0;
for (i = 0; i < n1; i++)
{
hashb1 = (hashb1 * p + b[i]) % MOD1,
hashb2 = (hashb2 * p + b[i]) % MOD2;
}
nr=0;
if (hashb1 == hasha1 && hashb2 == hasha2)
{
match[0] = 1;
nr++;
}
for (i = n1; i < n2; i++)
{
hashb1 = ((hashb1 - (b[i - n1] * p1) % MOD1 + MOD1) * p + b[i]) % MOD1;
hashb2 = ((hashb2 - (b[i - n1] * p2) % MOD2 + MOD2) * p + b[i]) % MOD2;
if (hashb1 == hasha1 && hashb2 == hasha2)
{
match[ i - n1 + 1 ] = 1;
nr++;
}
}
fout<<nr<<'\n';
nr = 0;
for (i = 0; i < n2 && nr < 1000; i++)
{
if (match[i])
{ nr++,
fout<<i<<" ";
}
}
fout<<'\n';
return 0;
}