Pagini recente » Cod sursa (job #2143448) | Cod sursa (job #2857247) | Cod sursa (job #2869107) | Cod sursa (job #1124598) | Cod sursa (job #950839)
Cod sursa(job #950839)
#include <fstream>
#include <cstring>
using namespace std;
#define mod1 1234
#define mod2 1235
#define p1 73
#define p2 74
char pe_cine[2000007];
char sir[2000007];
int mach[2000007];
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin.get(pe_cine,2000007);
cin.get();
cin.get(sir,2000007);
int n1=strlen(pe_cine),i;
int n2=strlen(sir);
if(n1>n2)
{
cout<<"0\n";
//cout<<"spec"<<endl;
//system("PAUSE");
cin.close();
cout.close();
return 0;
}
int hash_mic1=0,hash_mic2=0;
int hash_mare1=0,hash_mare2=0;
int coef1=1,coef2=1;
for(i=0;i<n1;i++)
{
hash_mic1=(hash_mic1*p1+pe_cine[i])%mod1;
hash_mare1=(hash_mare1*p1+sir[i])%mod1;
hash_mic2=(hash_mic2*p2+pe_cine[i])%mod2;
hash_mare2=(hash_mare2*p2+sir[i])%mod2;
if(i!=0)
{
coef1=(coef1*p1)%mod1;
coef2=(coef2*p2)%mod2;
}
//cout<<hash_mic1<<' '<<' '<<hash_mare1<<' '<<' '<<coef1<<' '<<endl;
}
int nr=0;
for(i=n1;i<n2;i++)
{
if(hash_mic1==hash_mare1 && hash_mic2==hash_mare2)
mach[nr++]=i-n1;
hash_mare1=(((((hash_mare1-(sir[i-n1]*coef1)%mod1+mod1)%mod1)*p1)%mod1+sir[i])%mod1);
hash_mare2=(((((hash_mare2-(sir[i-n1]*coef2)%mod2+mod2)%mod2)*p2)%mod2+sir[i])%mod2);
}
if(hash_mic1==hash_mare1 && hash_mic2==hash_mare2)
mach[nr++]=n2-n1;
cout<<nr<<'\n';
if(nr>1000)
nr=1000;
for(i=0;i<nr;i++)
cout<<mach[i]<<' ';
cout<<'\n';
cin.close();
cout.close();
// system("PAUSE");
return 0;
}