Pagini recente » Cod sursa (job #2209695) | Cod sursa (job #1733395) | Cod sursa (job #2674528) | Cod sursa (job #2028996) | Cod sursa (job #1983322)
#include <cstdio>
#include <cstring>
#define lgMax 2000000
#define posMax 1000
#define MOD1 666013
#define MOD2 1000003
#define BASE 63
using namespace std;
char A[lgMax+1], B[lgMax+1];
int pos[posMax+1];
int conv(char ch){
if (ch>='0' && ch<='9')
return ch-'0'+1;
if (ch>='a' && ch<='z')
return ch-'a'+11;
if (ch>='A' && ch<='Z')
return ch-'A'+37;
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", &A, &B);
int NA=strlen(A), NB=strlen(B);
if (NA>NB){
printf("0\n");
return 0;
}
int hashA1, hashA2, hashB1, hashB2;
hashA1=hashA2=hashB1=hashB2=0;
int P1, P2;
P1=P2=1;
for (int i=0; i<NA; i++){
hashA1=(hashA1*BASE+conv(A[i]))%MOD1;
hashA2=(hashA2*BASE+conv(A[i]))%MOD2;
hashB1=(hashB1*BASE+conv(B[i]))%MOD1;
hashB2=(hashB2*BASE+conv(B[i]))%MOD2;
if (i>0)
P1=(P1*BASE)%MOD1,
P2=(P2*BASE)%MOD2;
}
int nrPos=0;
if (hashA1==hashB1 && hashA2==hashB2)
pos[++nrPos]=0;
for (int i=NA; i<NB; i++){
hashB1=((hashB1 - (conv(B[i-NA]) * P1)%MOD1 + MOD1)*BASE + conv(B[i]))%MOD1;
hashB2=((hashB2 - (conv(B[i-NA]) * P2)%MOD2 + MOD2)*BASE + conv(B[i]))%MOD2;
if (hashA1==hashB1 && hashA2==hashB2){
nrPos++;
if (nrPos<=posMax)
pos[nrPos]=i-NA+1;
}
}
printf("%d\n", nrPos);
for (int i=1; i<=nrPos && i<=posMax; i++)
printf("%d ", pos[i]);
return 0;
}