Pagini recente » Cod sursa (job #1491408) | Cod sursa (job #533587) | Cod sursa (job #917023) | Cod sursa (job #428195)
Cod sursa(job #428195)
#include <cstdio>
#include <cstring>
#define NMAX 2000010
#define MMAX 2000010
#define MOD1 100003
#define MOD2 100019
#define P 73
int P1 = 1, P2 = 1;
int URM[MMAX];
char A[NMAX],B[MMAX];
int M, N;
int amod1, amod2;
int bmod1, bmod2;
int NR = 0;
int poz[NMAX];
void citire()
{
gets(A);
gets(B);
M = strlen(A);
while(!A[M - 1] || A[M - 1] == '\n' || A[M - 1] == EOF)
M--;
N = strlen(B);
while(!B[N - 1] || B[N - 1] == '\n' || B[N - 1] == EOF)
N--;
}
void obt()
{
for(int i = 0 ; i < M ; i++)
{
amod1 = (amod1 * P + A[i]) % MOD1;
amod2 = (amod2 * P + A[i]) % MOD2;
bmod1 = (bmod1 * P + B[i]) % MOD1;
bmod2 = (bmod2 * P + B[i]) % MOD2;
if(i)
{
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
}
if(amod1 == bmod1 && amod2 == bmod2)
poz[++NR] = 0;
}
void RK()
{
for(int i = M ; i < N ; i++)
{
bmod1 = ((bmod1 - (B[i - M] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
bmod2 = ((bmod2 - (B[i - M] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
if(amod1 == bmod1 && amod2 == bmod2)
poz[++NR] = i - M + 1;
}
}
void scrie()
{
printf("%d\n",NR);
for(int i = 1 ;i <= NR && i <= 1000 ; i++)
printf("%d ",poz[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
obt();
RK();
scrie();
return 0;
}