Pagini recente » Cod sursa (job #1229106) | Cod sursa (job #2523533) | Cod sursa (job #2583084) | Cod sursa (job #2168343) | Cod sursa (job #631712)
Cod sursa(job #631712)
#include<cstdio>
#include<cstring>
#define Mod 666013
#define Mod2 10003
using namespace std;
int i,nr,v1,v2,poz[2000001],n,m,p1,p2,s1,s2;
char a[2000002],b[2000002];
int main()
{
nr=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%d",&n);
gets(a+1);
m=strlen(a+1);
gets(b+1);
n=strlen(b+1);
p1=1;
p2=1;
s1=0;
s2=0;
v1=0;
v2=0;
for (i=1;i<=m;i++)
{
s1=(s1*137+a[i])%Mod;
s2=(s1*157+a[i])%Mod2;
v1=(v1*137+b[i])%Mod;
v2=(v2*157+b[i])%Mod2;
if (i<m)p1=(p1*137)%Mod;
if (i<m)p2=(p2*157)%Mod2;
}
if(v1==s1&&v2==s2)
{
nr++;
poz[nr]=i-m;
}
for (i=m+1;i<=n;i++)
{
v1=(((v1-b[i-m]*p1)%Mod+Mod)*137+b[i])%Mod;
v2=(((v2-b[i-m]*p2)%Mod2+Mod2)*157+b[i])%Mod2;
if(v1==s1&&v2==s2)
{
nr++;
poz[nr]=i-m;
}
}
printf("%d\n",nr);
if (nr>1000) nr=1000;
for (i=1;i<=nr;i++)
{
printf("%d ",poz[i]);
}
return 0;
}