Pagini recente » Cod sursa (job #2418733) | Cod sursa (job #2890095) | Cod sursa (job #2947111) | Cod sursa (job #1722380) | Cod sursa (job #1575959)
#include <cstdio>
#include <cstring>
#define B1 27
#define B2 29
#define MOD1 10007
#define MOD2 666013
using namespace std;
char X[2000020],Y[2000020];
int match[2000020],v1,v2,h1,h2,n,m,p1,p2,i,nr;
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
scanf ("%s",X);
scanf ("%s",Y);
m = strlen(X);
n = strlen(Y);
if ( m > n )
{
printf ("0\n");
return 0;
}
p1=p2=1;
v1=v2=0;
// se calculeaza valoarea sirului X
for (i=0; i<m; i++)
{
v1 = ( v1 * B1 + X[i]) % MOD1;
v2 = ( v2 * B2 + X[i]) % MOD2;
// se precalculeaza puterea la care un element va fi scos din sablon
if ( i!=1 )
{
p1 = ( p1 * B1 ) % MOD1;
p2 = ( p2 * B2 ) % MOD2;
}
}
h1=h2=0;
// se calculeaza valoarea primei subsecvente din Y
for (i=0; i<m; i++)
{
h1 = ( h1 * B1 + Y[i]) % MOD1;
h2 = ( h2 * B2 + Y[i]) % MOD2;
}
// se verifica daca valorile primei subsecvente coincid cu sablonul
if (h1 == v1 && h2 == v2)
{
nr++;
match[0] = 1;
}
// se contunua pana la finalul sirului X
for (i=m; i<n; i++)
{
h1 = ((h1 - (Y[i - m] * p1) % MOD1 + MOD1) * B1 + Y[i] ) % MOD1;
h2 = ((h2 - (Y[i - m] * p2) % MOD2 + MOD2) * B2 + Y[i] ) % MOD2;
if (h1 == v1 && h2 == v2)
{
nr++;
match[i - m +1] = 1;
}
}
printf ("%d\n",nr);
for (i = 0; i < n; i++)
if (match[i])
printf("%d ", i);
printf("\n");
return 0;
}