Pagini recente » Cod sursa (job #552785) | Cod sursa (job #1155769) | Cod sursa (job #554979) | Cod sursa (job #2131514) | Cod sursa (job #3204337)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char sir1[2000001],sir2[2000001];
int v[2000001];
int mod1=666013,mod2=1000003;
int putere(int n,int mod)
{
int rez=1,baza=62;
while(n!=0)
{
if(n%2==0)
{
baza=1ULL*baza*baza%mod;
n=n/2;
}
else
{
rez=1ULL*rez*baza%mod;
n--;
}
}
return rez%mod;
}
int main()
{
cin>>sir1>>sir2;
int n=strlen(sir1),m=strlen(sir2),i,nr1,nr2,nr3,nr4,cnt=0;
if(n>m)
cout<<0;
else
{
nr1=(sir1[0]*62%mod1+sir1[1]%mod1)%mod1;
nr2=(sir2[0]*62%mod2+sir2[1]%mod2)%mod2;
nr3=(sir1[0]*62%mod2+sir1[1]%mod2)%mod2;
nr4=(sir2[0]*62%mod1+sir2[1]%mod1)%mod1;
for(i=2;i<n;i++)
{
char x=sir1[i],y=sir2[i];
nr1+=(nr1*62%mod1+x%mod1)%mod1;
nr2+=(nr2*62%mod2+y%mod2)%mod2;
nr3+=(nr3*62%mod2+x%mod2)%mod2;
nr4+=(nr4*62%mod1+y%mod1)%mod1;
}
if(nr1==nr4 and nr2==nr3)
cnt++,v[cnt]=0;
for(i=n;i<m;i++)
{
nr2=(((nr2-(1LL*sir2[i-n]*putere(n-1,mod2)%mod2)+mod2)*62)%mod2+sir2[i])%mod2;
nr4=(((nr4-(1LL*sir2[i-n]*putere(n-1,mod1)%mod1)+mod1)*62)%mod1+sir2[i])%mod1;
if(nr1==nr4 and nr2==nr3)
cnt++,v[cnt]=i;
}
cout<<cnt<<"\n";
for(i=1;i<=cnt;i++)
cout<<v[i]<<" ";
}
return 0;
}