Pagini recente » Cod sursa (job #583340) | Cod sursa (job #352805) | Monitorul de evaluare | Cod sursa (job #1498044) | Cod sursa (job #3341995)
#include <fstream>
#include <cstring>
#define LGMAX 2000005
#define MOD1 1000000007
#define MOD2 1000000013
#define P 97
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[LGMAX], b[LGMAX];
int lg1, lg2, k, nr, st[1005], hasha1, hasha2, hashb1, hashb2, p1, p2;
int Poz(char x, int MOD)
{
int poz=x-'A'+1;
return poz%MOD;
}
int main()
{
fin>>a>>b;
lg1=strlen(a);
lg2=strlen(b);
p1=p2=1;
for(int i=0; i<lg1; i++)
{
hasha1=(hasha1*P%MOD1 + Poz(a[i], MOD1))%MOD1;
hasha2=(hasha2*P%MOD2 + Poz(a[i], MOD2))%MOD2;
hashb1=(hashb1*P%MOD1 + Poz(b[i], MOD1))%MOD1;
hashb2=(hashb2*P%MOD2 + Poz(b[i], MOD2))%MOD2;
if(i)
{
p1=(p1*P)%MOD1;
p2=(p2*P)%MOD2;
}
}
if(hasha1==hashb1 && hasha2==hashb2)
st[++nr]=0;
for(int i=lg1; i<lg2; i++)
{
hashb1=((hashb1+MOD1-p1*Poz(b[i-lg1], MOD1)%MOD1)%MOD1*P%MOD1+Poz(b[i], MOD1))%MOD1;
hashb2=((hashb2+MOD2-p2*Poz(b[i-lg1], MOD2)%MOD2)%MOD2*P%MOD2+Poz(b[i], MOD2))%MOD2;
//hash=(hash-p*Poz(b[i-lg1]))*P+Poz(b[i])
if(hasha1==hashb1 && hasha2==hashb2)
st[++nr]=i-lg1+1;
}
fout<<nr<<'\n';
for(int i=1; i<=nr && i<=1000; i++)
fout<<st[i]<<' ';
return 0;
}