Pagini recente » Cod sursa (job #1974002) | Cod sursa (job #2653452) | Cod sursa (job #1231115) | Cod sursa (job #651810) | Cod sursa (job #428188)
Cod sursa(job #428188)
#include <cstdio>
#include <cstring>
#define NMAX 2000005
#define MMAX 2000005
#define MOD1 100003
#define MOD2 100019
#define P 122
int P1 = 1, P2 = 1;
int URM[MMAX];
char A[NMAX],B[MMAX];
int N, M;
int amod1, amod2;
int bmod1, bmod2;
int NR = 0;
int poz[NMAX];
void citire()
{
scanf("%s%s",A,B);
N = strlen(A);
M = strlen(B);
}
void obt()
{
for(int i = 0 ; i < N ; 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 = N ; i < M ; i++)
{
bmod1 = ((bmod1 - (B[i - N] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
bmod2 = ((bmod2 - (B[i - N] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
if(amod1 == bmod1 && amod2 == bmod2)
poz[++NR] = i - N + 1;
}
}
void scrie()
{
printf("%d\n",NR);
for(int i = 1 ; i <= NR ; i++)
printf("%d ",poz[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
obt();
RK();
scrie();
return 0;
}