Pagini recente » Cod sursa (job #2064988) | Cod sursa (job #1871295) | Cod sursa (job #1744792) | Cod sursa (job #1602349) | Cod sursa (job #2030725)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
vector <int> rez;
int baza=73;
int MOD2=10000007;
int MOD=666013;
int hashA,hashB,hashB2,hashA2,cnt;
int main()
{
f>>A>>B;
int putere=1,putere2=1,i;
for(i=0; i<A.size(); i++)
{
hashA = (hashA*baza + A[i]) % MOD;
//hashA2 = (hashA2*baza + A[i]) % MOD2;
if(i!=0)
{
putere = (putere*baza)%MOD;
//putere2 = (putere2*baza)%MOD2;
}
}
for(i=0; i<A.size(); i++)
{
hashB = (hashB*baza+B[i]) % MOD;
//hashB2 = (hashB2*baza+B[i]) % MOD2;
}
if(hashA==hashB)
{
cnt++;
rez.push_back(0);
}
for(i=A.size(); i<B.size(); i++)
{
hashB = ((hashB - (B[i - A.size()] * putere) % MOD + MOD) * baza + B[i]) % MOD;
//hashB2 = ((hashB2 - (B[i - A.size()] * putere2) % MOD2 + MOD2) * baza + B[i]) % MOD2;
if(hashA==hashB)
{
cnt++;
if(cnt<=1000)
rez.push_back(i-A.size()+1);
}
}
g<<cnt<<'\n';
for(auto it:rez)
g<<it<<" ";
return 0;
}