Pagini recente » Cod sursa (job #2728243) | Cod sursa (job #2642627) | Cod sursa (job #2510603) | Cod sursa (job #2653426) | Cod sursa (job #3258904)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000000;
const int mod1 = 22211697;
const int mod2 = 22130121;
const int b = 91;
string A;
string B;
int este[NMAX+1];
int pow1 = 1, pow2 = 1;
int hashA1, hashA2;
int hashB1, hashB2;
int main()
{
fin >> A;
fin >> B;
int szA = A.size();
int szB = B.size();
for(int i=0; i<szA; i++)
{
if(i!=0)
pow1 = (pow1*b)%mod1,
pow2 = (pow2*b)%mod2;
hashA1 = (hashA1*b + A[i])%mod1;
hashA2 = (hashA2*b + A[i])%mod2;
}
int cnt = 0;
for(int i=0; i<szA; i++)
hashB1 = (hashB1*b + B[i])%mod1,
hashB2 = (hashB2*b + B[i])%mod2;
if(hashA1 == hashB1 && hashA2 == hashB2)
este[0] = 1, cnt++;
for(int i=szA; i<szB; i++)
{
hashB1 = ((hashB1 - 1ll*B[i-szA]*pow1)%mod1*b+B[i])%mod1;
hashB2 = ((hashB2 - 1ll*B[i-szA]*pow2)%mod2*b+B[i])%mod2;
//cout << hashB1 << ' ' << hashB2 << '\n';
if(hashA1 == hashB1 && hashA2 == hashB2)
este[i-szA+1] = 1, cnt++;
}
fout << cnt << '\n';
cnt = 0;
for(int i=0; i<szB && cnt<=1000; i++)
if(este[i])
fout << i << ' ', cnt++;
return 0;
}