Pagini recente » Cod sursa (job #3347872) | Cod sursa (job #352210) | Cod sursa (job #1900401) | Cod sursa (job #3329934) | Cod sursa (job #2370530)
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
typedef long long ll;
const ll MOD1=1000000007;
const ll MOD2=994366432;
const ll P1=997898399;
const ll P2=859925329;
string a,b;
ll hashA1,hashA2,hashB1,hashB2;
ll p1,p2;
void precalculate()
{
p1=1;
p2=1;
for(int i=0;i<a.length();i++)
{
p1=(p1*P1)%MOD1;
p2=(p2*P2)%MOD2;
hashA1=(hashA1*P1+a[i])%MOD1;
hashA2=(hashA2*P2+a[i])%MOD2;
hashB1=(hashB1*P1+b[i])%MOD1;
hashB2=(hashB2*P2+b[i])%MOD2;
}
}
int nr;
int main()
{
fin>>a>>b;
vector<int> poz;
int aL=a.length();
int bL=b.length();
if(aL>bL)
{
fout<<"0\n";
return 0;
}
precalculate();
// fout<<hashish<<" "<<hashing(5,7);
for(int i=0;i<=bL-aL;i++)
{
if(hashA1==hashB1&&hashA2==hashB2)
{
poz.push_back(i);
nr++;
}
hashB1=(hashB1*P1+b[i+aL]-(b[i]*p1)%MOD1)%MOD1;
hashB2=(hashB2*P2+b[i+aL]-(b[i]*p2)%MOD2)%MOD2;
}
fout<<nr<<'\n';
for(int i=0;i<min((int)poz.size(),1000);i++)
{
fout<<poz[i]<<' ';
}
return 0;
}