Pagini recente » Cod sursa (job #2145210) | Cod sursa (job #2581797) | Cod sursa (job #368597) | Cod sursa (job #255185) | Cod sursa (job #3279835)
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int BAZA1=521;
const int BAZA2=523;
const int MOD1=666013;
const int MOD2=312013;
int rasp[2000005];
long long hash_(string s, const int MOD, const int BAZA)
{
long long galeata=0;
long long put=1;
for(int i=0;i<s.size();i++)
{
galeata=(galeata+(((s[i]-'0')%10)*put)%MOD)%MOD;
put=(put*BAZA)%MOD;
}
return galeata;
}
int main()
{
string A,B;
cin>>A>>B;
int n=A.size(), m=B.size();
int codA1=0, codA2=0;
codA1=hash_(A, MOD1, BAZA1);
codA2=hash_(A, MOD2, BAZA2);
int nrrasp=0;
int codB1=0, codB2=0;
for(int i=0;i+n-1<m;i++)
{
codB1=hash_(B.substr(i, n), MOD1, BAZA1);
codB2=hash_(B.substr(i,n), MOD2, BAZA2);
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;
}