Pagini recente » Rezultate Info Oltenia 2018 Proba Individuala | Cod sursa (job #1319243) | Cod sursa (job #3179732) | Cod sursa (job #2621122) | Cod sursa (job #2675822)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
unsigned long long MOD=666013;
unsigned long long B=127;
string a,b;
unsigned long long hashA,hashB,powe;
unsigned long long sol;
int ans[1005],poz;
void make_hash()
{
powe=1;
for(unsigned long long i=0;i<a.length();i++)
{
hashA=(hashA * B + a[i]) % MOD;
powe=(powe * B) % MOD;
}
for(unsigned long long i=0;i<a.length();i++)
hashB=(hashB * B + b[i]) % MOD;
}
int main()
{
in>>a>>b;
if(a.size()>b.size())
{
out<<"0";
return 0;
}
make_hash();
if(hashA == hashB)
{
sol++;
ans[++poz]=0;
}
for(unsigned long long i=1;i<=b.size()-a.size();i++)
{
hashB=(hashB * B+b[i+a.size()-1]) % MOD;
unsigned long long aux=(powe * b[i-1])%MOD;
hashB=(hashB-aux+MOD) % MOD;
if(hashA==hashB)
{
sol++;
if(poz<=1000)
ans[++poz]=i;
}
}
out<<sol<<"\n";
for(int i=1;i<=poz;i++)
out<<ans[i]<<" ";
return 0;
}