Pagini recente » Cod sursa (job #1243437) | Cod sursa (job #1855189) | Cod sursa (job #1187885) | Cod sursa (job #3290080) | Cod sursa (job #2045917)
#include <fstream>
#include <cstring>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
char A[MAXN],B[MAXN];
char match[MAXN];
int main()
{ f>>A>>B;
int NA=strlen(A),NB=strlen(B);
if(NA>NB) {g<<"0\n"; g.close(); return 0;}
int P1=1,P2=1,ha1=0,ha2=0,hb1=0,hb2=0;
for(int i =0;i<NA;i++)
{ ha1=(ha1*P+A[i])%MOD1; ha2=(ha2*P+A[i])%MOD2;
hb1=(hb1*P+B[i])%MOD1; hb2=(hb2*P+B[i])%MOD2;
if(i) {P1=(P1*P)%MOD1; P2=(P2*P)%MOD2;}
}
int Nr = 0;
if(hb1==ha1 && hb2==ha2) {match[0]=1; Nr++;}
for(int 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) {match[i-NA+1]=1; Nr++;}
}
g<<Nr<<'\n';
Nr=0;
for(int i=0;i<NB && Nr<1000;i++)
if(match[i]) {Nr++; g<<i<<' ';}
g<<'\n'; g.close(); return 0;
}