Pagini recente » Cod sursa (job #445620) | Autentificare | Cod sursa (job #1340514) | Cod sursa (job #3149740) | Cod sursa (job #2730943)
#include <bits/stdc++.h>
using namespace std;
const int prime1 = 666013;
const int prime2 = 666067;
string verif;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void gaseste(string subs, string s)
{
int hashSubs1 = 0, putere1 = 1;
int hashSubs2 = 0, putere2 = 1;
for(int i = 0; i < subs.size(); i++)
{
hashSubs1 = (26 * hashSubs1 + subs[i]) % prime1;
hashSubs2 = (26 * hashSubs2 + subs[i]) % prime2;
if(i)
{
putere1 = (putere1 * 26) % prime1;
putere2 = (putere2 * 26) % prime2;
}
}
int hashS1 = 0;
int hashS2 = 0;
for(int i = 0; i < subs.size(); i++)
{
hashS1 = (26 * hashS1 + s[i]) % prime1;
hashS2 = (26 * hashS2 + s[i]) % prime2;
}
int ans = 0;
if(hashSubs1 == hashS1 and hashSubs2 == hashS2)
{
verif[0] = 1;
ans++;
}
for(int i = subs.size(); i < s.size(); i++)
{
hashS1 = ((hashS1 - (s[i - subs.size()] * putere1) % prime1 + prime1) * 26 + s[i]) % prime1;
hashS2 = ((hashS2 - (s[i - subs.size()] * putere2) % prime2 + prime2) * 26 + s[i]) % prime2;
if(hashSubs1 == hashS1 and hashSubs2 == hashS2)
{
verif[i - subs.size() + 1] = 1;
ans++;
}
}
out << ans << "\n";
for(int i = 0; i < s.size(); i++)
if(verif[i])
out << i << " ";
}
int main()
{
string subs, s;
in >> subs;
in >> s;
gaseste(subs, s);
return 0;
}