Pagini recente » Cod sursa (job #417805) | Cod sursa (job #232527) | Cod sursa (job #2666870) | Cod sursa (job #2974341) | Cod sursa (job #340382)
Cod sursa(job #340382)
#include <cstdio>
#include <cstring>
#define MAX_N 2000005
#define MOD1 100007
#define MOD2 100021
#define P 73
int match[MAX_N], nrm;
char A[MAX_N], B[MAX_N];
int main()
{
freopen("strmatch.in","rt",stdin);
freopen("strmatch.out","wt",stdout);
scanf("%s\n%s",A, B);
int N = strlen(A);
int M = strlen(B);
int h1 = 0, H1 = 0, h2 = 0, H2 = 0, P1 = 1, P2 = 1;
for(int i = 0; i < N; ++i)
{
h1 = (h1*P + A[i]) % MOD1;
h2 = (h2*P + A[i]) % MOD2;
H1 = (H1*P + B[i]) % MOD1;
H2 = (H2*P + B[i]) % MOD2;
if(i)
P1 = (P1 * P) % MOD1,
P2 = (P2 * P) % MOD2;
}
if(H1 == h1 && H2 == h2)
match[++nrm] = 1;
for(int i = N; i < M; ++i)
{
H1 = ((H1 - (B[i-N]*P1) % MOD1 + MOD1)*P + B[i]) % MOD1;
H2 = ((H2 - (B[i-N]*P2) % MOD2 + MOD2)*P + B[i]) % MOD2;
if(H1 == h1 && H2 == h2)
match[++nrm] = i - N + 1;
}
printf("%d\n",nrm);
for(int i = 1; i <= nrm && i <= 1000; ++i)
printf("%d ", match[i]);
}