Pagini recente » Cod sursa (job #1098796) | Cod sursa (job #749158) | Cod sursa (job #946631) | Cod sursa (job #806330) | Cod sursa (job #896074)
Cod sursa(job #896074)
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int a1,a2,b1,b2,bz=31,m1=100007,m2=666013,p1=1,p2=1,l1,l2,nr;
char a[2000000],b[2000000];
vector <int> poz;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
l1=strlen(a);
l2=strlen(b);
for(int i=1;i<l1;i++)
{
p1=(p1*bz)%m1;
p2=(p2*bz)%m2;
}
for(int i=0;i<l1;i++)
{
a1=(a1*bz+a[i])%m1;
a2=(a2*bz+a[i])%m2;
b1=(b1*bz+b[i])%m1;
b2=(b2*bz+b[i])%m2;
}
if(a1==b1||a2==b2) poz.push_back(0);
for(int i=l1;i<l2;i++)
{
b1=((b1+m1-((p1)*b[i-l1])%m1)*bz+b[i])%m1;
b2=((b2+m2-((p2)*b[i-l1])%m2)*bz+b[i])%m2;
if(a1==b1||a2==b2) poz.push_back(i-l1+1);
if(poz.size()==1000) break;
}
printf("%d\n",poz.size());
for(int i=0;i<poz.size();i++)
printf("%d ",poz[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}