Pagini recente » Cod sursa (job #2570717) | Cod sursa (job #2634627) | Cod sursa (job #3122653) | Cod sursa (job #2347158) | Cod sursa (job #2675676)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
unsigned int MOD=666013;
unsigned int B=700001;
string a,b;
unsigned long long hashA,hashB,powe;
int sol;
vector<int> ans;
void make_hash()
{
powe=1;
for(int i=0;i<a.length();i++)
{
hashA=(hashA * B + a[i]) % MOD;
powe=(powe * B) % MOD;
}
for(int i=0;i<a.length();i++)
hashB=(hashB * B + b[i]) % MOD;
}
int main()
{
in>>a>>b;
make_hash();
if(hashA == hashB)
{
sol++;
ans.push_back(0);
}
for(int i=1;i<=b.size()-a.size();i++)
{
hashB=(hashB * B+b[i+a.size()-1]) % MOD;
hashB=(hashB-((powe * b[i-1]) % MOD) + MOD) % MOD;
if(hashA==hashB)
{
sol++;
if(sol<1000)
ans.push_back(i);
}
}
out<<sol<<"\n";
for(auto x:ans)
out<<x<<" ";
return 0;
}