Pagini recente » Borderou de evaluare (job #1566660) | Cod sursa (job #851644) | Borderou de evaluare (job #1585371) | Borderou de evaluare (job #913421) | Cod sursa (job #3340604)
#include <fstream>
#include <string>
#include <vector>
#define int long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MOD1 = 666013, MOD2 = 1e6+7, p = 97;
int nr;
string a, b;
vector<int> v;
int poz, i, hash_a_1, hash_a_2, hash_b_1, hash_b_2, p1, p2;
int32_t main()
{
getline(in, a);
getline(in, b);
if (a.size() > b.size())
{
out << 0;
return 0;
}
p1 = p2 = 1;
for (i = 0; i < a.size(); i++)
{
hash_a_1 = ((hash_a_1*p)%MOD1 + a[i]%MOD1)%MOD1;
hash_a_2 = ((hash_a_2*p)%MOD2 + a[i]%MOD2)%MOD2;
hash_b_1 = ((hash_b_1*p)%MOD1 + b[i]%MOD1)%MOD1;
hash_b_2 = ((hash_b_2*p)%MOD2 + b[i]%MOD2)%MOD2;
if (i > 0)
{
p1 = (p1*p)%MOD1;
p2 = (p2*p)%MOD2;
}
}
if (hash_a_1 == hash_b_1 && hash_a_2 == hash_b_2)
{
v.push_back(0);
nr++;
}
for (i = a.size(); i < b.size(); i++)
{
hash_b_1 = (((hash_b_1 + MOD1 - (b[i-a.size()]*p1)%MOD1)*p%MOD1)+b[i])%MOD1;
hash_b_2 = (((hash_b_2 + MOD2 - (b[i-a.size()]*p2)%MOD2)*p%MOD2)+b[i])%MOD2;
if (hash_a_1 == hash_b_1 && hash_a_2 == hash_b_2)
{
if (nr < 1000)
v.push_back(i-a.size()+1);
nr++;
}
}
out << nr << '\n';
for (auto ind : v)
out << ind << ' ';
return 0;
}