Pagini recente » Cod sursa (job #840435) | Cod sursa (job #2174844) | Cod sursa (job #2225851) | Cod sursa (job #1390372) | Cod sursa (job #1519377)
#include<cstdio>
#include<cstring>
using namespace std;
char s1[2000001],s2[2000001];
int n1=666013,n2=100007,b=123,v[1002];
bool verif(int n,int i)
{
int pp=1;
for(int j=0;j<=n;j++)
{
if(s1[j]!=s2[j+i])
pp=0;
}
return pp;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
long long n,m,i,p1=1,p2=1,k1=0,k2=0,kk1=0,kk2=0,sum=0;
scanf("%s%s",&s1,&s2);
n=strlen(s1);
n--;
m=strlen(s2);
m--;
for(i=n;i>=0;i--)
{
k1+=(s1[i]*p1)%n1;
k1%=n1;
k2+=(s1[i]*p2)%n2;
k2%=n2;
kk1+=(s2[i]*p1)%n1;
kk1%=n1;
kk2+=(s2[i]*p2)%n2;
kk2%=n2;
if(i)
{
p1=(p1*b)%n1;
p2=(p2*b)%n2;
}
}
for(i=n+1;i<=m;i++)
{
if(k1==kk1&&k2==kk2)
{
if(verif(n,i-n-1)==1)
{
if(sum<=1000)
{
sum++;
v[sum]=i-n-1;
}
}
}
kk1-=(s2[i-n-1]*p1)%n1;
kk1%=n1;
if(kk1<0)
{
kk1+=n1;
}
kk2-=(s2[i-n-1]*p2)%n2;
kk2%=n2;
if(kk2<0)
{
kk2+=n2;
}
kk1=(kk1*p1)%n1;
kk1+=s2[i];
kk1%=n1;
kk2=(kk2*p2)%n2;
kk2+=s2[i];
kk2%=n2;
}
printf("%d\n",sum);
for(i=1;i<=sum;i++)
{
printf("%d ",v[i]);
}
return 0;
}