Pagini recente » Cod sursa (job #2491702) | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3333847)
#include <bits/stdc++.h>
#define NMAX 2000000
#define P 73
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MOD[3]={1000000007, 1000000009, 666013};
int p[3]={1, 1, 1};
int hash_a[3], hash_b[3];
bitset<NMAX+1> potrivire;
int main()
{
string a, b;
in >> a >> b;
for(int i=0; i<a.size(); i++)
{
for(int j=0; j<3; j++)
{
hash_a[j]=(1ll*hash_a[j]*P + a[i])%MOD[j];
if(i>0) p[j]=(1ll*p[j]*P)%MOD[j];
}
}
int nr_potriviri=0;
for(int i=0; i<b.size(); i++)
{
for(int j=0; j<3; j++)
{
if(i>=a.size())
hash_b[j]=((hash_b[j] - (1ll*b[i-a.size()]*p[j])%MOD[j] + MOD[j])*P + b[i])%MOD[j];
else
hash_b[j]=(1ll*hash_b[j]*P + b[i])%MOD[j];
}
if(i>=a.size()-1)
{
potrivire[i-a.size()+1]=(hash_a[0]==hash_b[0] && hash_a[1]==hash_b[1] && hash_a[2]==hash_b[2]);
if(potrivire[i-a.size()+1]==1) nr_potriviri++;
}
}
out << nr_potriviri << "\n";
nr_potriviri=0;
for(int i=0; i<b.size(); i++)
{
if(potrivire[i]==1)
{
out << i << " ";
nr_potriviri++;
}
if(nr_potriviri==1000) break;
}
return 0;
}