Pagini recente » Cod sursa (job #1834044) | Cod sursa (job #241373) | Cod sursa (job #2171109) | Cod sursa (job #460416) | Cod sursa (job #3258927)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000000;
const int mod1 = 100007;
const int mod2 = 100021;
const int b = 73;
string A;
string B;
int este[NMAX+1];
int pow1 = 1, pow2 = 1;
int hashA1, hashA2;
int hashB1, hashB2;
int main()
{
ios::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
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 - (B[i-szA]*pow1) % mod1 + mod1)*b+B[i])%mod1;
hashB2 = ((hashB2 - (B[i-szA]*pow2) % mod2 + mod2)*b+B[i])%mod2;
//cout << hashB1 << ' ' << hashB2 << '\n';
if(hashA1 == hashB1 && hashA2 == hashB2)
este[i-szA+1] = 1, cnt++;
}
fout << cnt << '\n';
cnt = 1;
for(int i=0; i<szB && cnt<1000; i++)
if(este[i])
fout << i << ' ', cnt++;
return 0;
}