Pagini recente » Cod sursa (job #2402566) | Istoria paginii runda/adfwgscv/clasament | Cod sursa (job #2359170) | Cod sursa (job #1674688) | Cod sursa (job #2047060)
#include <fstream>
#include <cstring>
#define MAXN 2000001
#define X 73
#define MOD 100007
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 P=1,ha=0,hb=0;
for(int i=0;i<NA;i++)
{ ha=(ha*X+A[i])%MOD;
hb=(hb*X+B[i])%MOD;
if(i)P=P*X%MOD;
}
int Nr=0;
if(hb==ha) {match[0]=1; Nr++;}
for(int i=NA;i<NB;i++)
{ hb=((hb-(B[i-NA]*P)% MOD+MOD)*X+B[i])%MOD;
if(hb==ha) {match[i-NA+1]=1; Nr++;}
}
g<<Nr<<'\n';
for(int i=0;i<NB && Nr;i++)
if(match[i]) {Nr--; g<<i<<' ';}
g<<'\n'; g.close(); return 0;
}