Pagini recente » Cod sursa (job #2670896) | Cod sursa (job #1081006) | Cod sursa (job #867857) | Cod sursa (job #870262) | Cod sursa (job #1262293)
#include <cstdio>
#include <cstring>
#define Nmax 20000001
#define b1 27
#define b2 29
#define mod1 10007
#define mod2 666013
char x[Nmax], y[Nmax];
int v1, v2, p1, p2, v[Nmax];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int n, m, i;
//citire
scanf("%s%s", &x, &y);
n = strlen(x);
m = strlen(y);
// daca primul sir e mai mare decat al 2-lea nu are rost sa mai cautam
if(n > m)
{
printf("%d", 0);
return 0;
}
p1 = p2 = 1;
for(i = 0; i<n; i++)
{
v1 = (v1 * b1 + x[i])% mod1;
v2 = (v2 * b2 + x[i])% mod2;
if(i >= 1)
{
p1 = (p1 * b1)%mod1;
p2 = (p2 * b2)%mod2;
}
}
int h1, h2;
h1 = h2 = 0;
for(i = 0; i<n; i++)
{
h1 = (h1 * b1 + y[i])%mod1;
h2 = (h2 * b2 + y[i])%mod2;
}
int nr = 0;
if(v1 == h1 && v2 == h2)
{
nr ++;
v[nr] = 0;
}
for(i =n; i<=m; i++)
{
h1=((h1-(y[i-n]*p1)%mod1+mod1)*b1+y[i])%mod1;
h2=((h2-(y[i-n]*p2)%mod2+mod2)*b2+y[i])%mod2;
if(h1 == v1 && v2 == h2)
{
nr ++;
v[nr] = i - n + 1;
}
}
printf("%d\n", nr );
for (i=1;i<=nr && i<=1000;i++)
printf("%d ", v[i]);
return 0;
}