Pagini recente » Cod sursa (job #716867) | Cod sursa (job #358779) | Cod sursa (job #766327) | Cod sursa (job #1667699) | Cod sursa (job #3208848)
#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=1LL*baza*baza%mod;
n=n/2;
}
else
{
rez=1LL*rez*baza%mod;
n--;
}
}
return rez;
}
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=0;
nr2=0;
nr3=0;
nr4=0;
for(i=0;i<n;i++)
{
nr1= (1LL*nr1*62+sir1[i])%mod1;
nr2= (1LL*nr2*62+sir1[i])%mod2;
///al doilea sir
nr3= (1LL*nr3*62+sir2[i])%mod1;
nr4= (1LL*nr4*62+sir2[i])%mod2;
}
if(nr1==nr3 and nr2==nr4)
cnt++,v[cnt]=0;
int p1=putere(n-1,mod1);
int p2=putere(n-1,mod2);
for(i=n;i<m;i++)
{
nr3=((nr3-1LL*sir2[i-n]*p1%mod1+mod1)*62%mod1+sir2[i])%mod1;
nr4=((nr4-1LL*sir2[i-n]*p2%mod2+mod2)*62%mod2+sir2[i])%mod2;
if(nr1==nr3 and nr2==nr4)
{
cnt++;
if(cnt<=1000)
v[cnt]=i-n+1;
}
}
cout<<cnt<<"\n";
for(i=1;i<=cnt && i<=1000;i++)
cout<<v[i]<<" ";
}
return 0;
}