Pagini recente » Cod sursa (job #1919427) | Cod sursa (job #1412251) | Cod sursa (job #1914226) | Cod sursa (job #2457691) | Cod sursa (job #2370498)
#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();
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(auto x:poz)
fout<<x<<' ';
return 0;
}