Pagini recente » Clasament FMI No Stress 2012 | Cod sursa (job #2941487) | Cod sursa (job #2184325) | Cod sursa (job #2042087) | Cod sursa (job #3279825)
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int BAZA1=67;
const int BAZA2=73;
const int MOD1=999983;
const int MOD2=999979;
int rasp[2000005];
long long hash1(string s)
{
long long galeata=0;
long long put=1;
for(int i=s.size();i>0;i--)
{
galeata=(galeata+(((s[i]-'0')%10)*put)%MOD1)%MOD1;
put=(put*BAZA1)%MOD1;
}
return galeata;
}
long long hash2(string s)
{
long long galeata=0;
long long put=1;
for(int i=s.size();i>0;i--)
{
galeata=(galeata+(((s[i]-'0')%10)*put)%MOD2)%MOD2;
put=(put*BAZA2)%MOD2;
}
return galeata;
}
long long recalc_hash(int &galeata, int scot, int adun, int p, int baza, int mod)
{
galeata=(galeata-(scot*p)%mod)%mod;
galeata=(galeata*baza)%mod;
galeata=(galeata+(adun*p)%mod)%mod;
return galeata;
}
int main()
{
string A,B;
cin>>A>>B;
int n=A.size(), m=B.size();
int codA1=0, codA2=0;
codA1=hash1(A);
codA2=hash2(A);
int nrrasp=0;
int codB1=0, codB2=0;
codB1=hash1(B.substr(0, n-1));
codB2=hash2(B.substr(0, n-1));
if(codB1==codA1 && codB2==codA2)
{
nrrasp++;
rasp[nrrasp]=0;
}
long long p1=pow(BAZA1, n-1);
long long p2=pow(BAZA2, n-1);
for(int i=1;i+n-1<m;i++)
{
recalc_hash(codB1, B[i-1], B[i+n-1], p1, BAZA1, MOD1);
recalc_hash(codB2, B[i-1], B[i+n-1], p2, BAZA2, MOD2);
if(codB1==codA1 && codB2==codA2)
{
nrrasp++;
rasp[nrrasp]=i;
}
}
cout<<nrrasp<<'\n';
for(int i=1;i<=min(nrrasp, 1000);i++)
cout<<rasp[i]<<" ";
return 0;
}