Pagini recente » Cod sursa (job #2839971) | Cod sursa (job #392252) | Cod sursa (job #1776515) | Cod sursa (job #1529) | Cod sursa (job #1262297)
#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 p1,v1,p2,v2,h1,h2, v[Nmax], nr;
int main()
{
int n,m, i;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", &x, &y);
n = strlen(x);
m = strlen(y);
// printf("%s", x);
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;
}
}
h1 = h2 = 0;
for(i = 0; i<n; i++)
{
h1 = (h1 * b1 + y[i])%mod1;
h2 = (h2 * b2 + y[i])%mod2;
}
nr = 0;
if(v1 == h1 && h2 == v2)
{
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;
}