Pagini recente » Cod sursa (job #1973443) | Cod sursa (job #2266102) | Cod sursa (job #1516407) | Cod sursa (job #68132) | Cod sursa (job #1516598)
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int n1=100007,n2=100021,lmax=2000000;
char s1[lmax],s2[lmax];
int v[1001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int nr1s2,nr2s2,i,k1,k2,nr1s1,nr2s1;
scanf("%s",&s2);
scanf("%s",&s1);
k1=strlen(s1);k2=strlen(s2);
nr1s2=nr2s2=0;
for(i=0;i<k2;i++)
{
nr1s2=((nr1s2*123)%n1+s2[i])%n1;
nr2s2=((nr2s2*123)%n2+s2[i])%n2;
}
for(i=0;i<k1;i++)
{
nr1s1=((nr1s1*123)%n1+s2[i])%n1;
nr2s1=((nr2s1*123)%n2+s2[i])%n2;
}
int p1=1,p2=pow(123,k2-1),j,k,poz=0;
bool pp=true;
nr1s1=nr2s1=0;
for(j=0;j<k1-k2;j++)
{
nr1s1-=s2[j]*p1;
nr2s1-=s2[j]*p1;
nr1s1%=n1;
nr2s1%=n2;
while(nr1s1<0)
nr1s1+=n1;
while(nr2s1<0)
nr2s1+=n2;
p1*=123;p1%=n1;
nr1s1+=s2[j+k2]*p2;
nr2s1+=s2[j+k2]*p2;
while(nr1s1<0)
nr1s1+=n1;
while(nr2s1<0)
nr2s1+=n2;
p2*=123;p2%=n1;
if(nr1s2!=nr1s1||nr2s2!=nr2s1)
{
pp=false;
}
else
{
v[++poz]=j;
}
}
printf("%d\n",poz);
for(i=1;i<=poz;i++)
{
printf("%d ",v[i]);
}
return 0;
}