Pagini recente » Cod sursa (job #2411855) | Rating Potinteu Minail (potytzu) | Cod sursa (job #3298599) | Cod sursa (job #3266773) | Cod sursa (job #895491)
Cod sursa(job #895491)
#include <cstdio>
# include <cstring>
# define b1 27
# define b2 29
# define mod1 10007
# define mod2 666013
using namespace std;
int n,m,i,p1,p2,v1,v2,h1,h2,nr,nr1;
char s[2000010],str[2000010];
bool match[2000010];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",s,str);
m=strlen(s);
n=strlen(str);
p1=p2=1;
if (m>n)
{
printf("%d\n",0);
return 0;
}
for (i=0; i<m; i++)
{
v1=(v1*b1+s[i])%mod1;
v2=(v2*b2+s[i])%mod2;
if (i!=1)
{
p1=(p1*b1)%mod1;
p2=(p2*b2)%mod2;
}
}
for (i=0; i<m; i++)
{
h1=(h1*b1+str[i])%mod1;
h2=(h2*b2+str[i])%mod2;
}
if (h1==v1 && h2==v2)
{
nr++;
match[0]=true;
}
for (i=m; i<n; i++)
{
h1=((h1-(str[i-m]*p1)%mod1+mod1)*b1+str[i])%mod1;
h2=((h2-(str[i-m]*p2)%mod2+mod2)*b2+str[i])%mod2;
if (h1==v1 && h2==v2)
{
nr++;
match[i-m+1]=true;
}
}
printf("%d\n",nr);
for (i=0; i<n && nr1<1000; i++)
if (match[i]==true)
{
nr1++;
printf("%d ",i);
}
printf("\n");
return 0;
}