Pagini recente » Profil CodinPacuraru | Istoria paginii utilizator/oanamaria | Atasamentele paginii rezolvarijudeteana | Monitorul de evaluare | Cod sursa (job #228514)
Cod sursa(job #228514)
#include <stdio.h>
#include <string.h>
#define MAXN 2000001
#define P 73
#define mod1 100007
#define mod2 100021
char a[MAXN], b[MAXN];
int h1A,h2A,h1B,h2B;
int P1,P2;
int nr;
int k;
int la,lb;
char poz[MAXN];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s",&a,&b);
la = strlen(a);
lb = strlen(b);
P1 = P2 = 1;
for(int i = 0; i < la; i++)
{
h1A = (h1A * P + a[i]) % mod1;
h2A = (h2A * P + a[i]) % mod2;
h1B = (h1B * P + b[i]) % mod1;
h2B = (h2B * P + b[i]) % mod2;
if (i != 0)
{
P1 = (P1 * P) % mod1;
P2 = (P2 * P) % mod2;
}
}
for(int i = 0; i <= lb-la; i++)
{
if ((h1A == h1B) && (h2A == h2B))
{
k++;
poz[i] = 1;
}
h1B = ((h1B - (P1 * b[i]) % mod1 + mod1) * P + b[i+la]) % mod1;
h2B = ((h2B - (P2 * b[i]) % mod2 + mod2) * P + b[i+la]) % mod2;
}
printf("%d \n",k);
for(int i = 0; ; i++)
{
if (poz[i]) printf("%d ",i);
nr+= poz[i];
if (nr == 1000) break;
if (nr == k) break;
}
return 0;
}