Pagini recente » Cod sursa (job #106617) | Cod sursa (job #1892698) | Cod sursa (job #527305) | Cod sursa (job #2487862) | Cod sursa (job #613351)
Cod sursa(job #613351)
#include <cstdio>
#include <string.h>
char s1[2000005],s2[2000005];
bool ok[2000005];
int n1,n2,h1,h2,hh1,hh2,i,p1,p2,mod1,mod2,nr,p;
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
scanf ("%s %s", s1, s2);
n1 = strlen (s1);
n2 = strlen (s2);
if (n1 > n2)
{
printf ("0/n");
return 0;
}
p1 = p2 = 1;
h1 = h2 = 0;
mod1 = 100007;
mod2 = 100021;
p = 73;
for (i=0; i<n1; i++)
{
h1 = (h1 * p + s1[i]) % mod1;
h2 = (h2 * p + s1[i]) % mod2;
if (i!=0)
{
p1 = (p1 * p) % mod1;
p2 = (p2 * p) % mod2;
}
}
hh1 = hh2 = 0;
for (i=0; i<n1; i++)
{
hh1 = (hh1 * p + s2[i]) % mod1;
hh2 = (hh2 * p + s2[i]) % mod2;
}
nr=0;
if (hh1 == h1 && hh2 == h2)
{
ok[0] = true;
nr++;
}
for (i=n1; i<n2; i++)
{
hh1 = ((hh1 - (s2[i-n1] * p1) % mod1 + mod1) * p + s2[i]) % mod1;
hh2 = ((hh2 - (s2[i-n1] * p2) % mod2 + mod2) * p + s2[i]) % mod2;
if (hh1 == h1 && hh2 == h2)
{
ok[i - n1 + 1] = true;
nr++;
}
}
printf ("%d\n",nr);
nr=0;
for (i = 0; i < n2 && nr < 1000; i++)
if (ok[i] == true)
{
nr++;
printf("%d ", i);
}
printf("\n");
return 0;
}