Pagini recente » Cod sursa (job #2918613) | Cod sursa (job #3231916) | Cod sursa (job #234641) | Clasament preONI 2007, Clasa a 9-a si gimnaziu | Cod sursa (job #2777194)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int generalHash1;
int generalHash2;
vector <int> pos;
const int MOD1 = 664918;
const int MOD2 = 5762209;
const int BASE1 = 139;
const int BASE2 = 131;
int Hash(string str, const int& modulo, const int& base)
{
long long myHash = 0;
for (int i = 0; i < str.size(); i++)
{
myHash *= base;
myHash += str[i];
myHash %= modulo;
}
return myHash;
}
int main()
{
fin >> a >> b;
generalHash1 = Hash(a, MOD1, BASE1);
generalHash2 = Hash(a, MOD2, BASE2);
if (a.size() > b.size())
{
fout << 0 << '\n';
}
int currentHash1 = Hash(b.substr(0, a.size()), MOD1, BASE1);
int currentHash2 = Hash(b.substr(0, a.size()), MOD2, BASE2);
if (generalHash1 == currentHash1 && generalHash2 == currentHash2)
{
pos.push_back(0);
}
int basePow1 = 1;
int basePow2 = 1;
for (int i = 1; i < a.size(); i++)
{
basePow1 *= BASE1;
basePow1 %= MOD1;
basePow2 *= BASE2;
basePow2 %= MOD2;
}
for (int i = a.size(); i < b.size(); i++)
{
int index = i - a.size();
int x1 = (b[index] * basePow1) % MOD1;
currentHash1 = ((currentHash1 - x1 + MOD1) % MOD1) * BASE1;
currentHash1 += b[i];
currentHash1 %= MOD1;
int x2 = (b[index] * basePow2) % MOD2;
currentHash2 = ((currentHash2 - x2 + MOD2) % MOD2) * BASE2;
currentHash2 += b[i];
currentHash2 %= MOD2;
if (generalHash1 == currentHash1 && generalHash2 == currentHash2)
{
pos.push_back(index + 1);
}
}
fout << pos.size() << '\n';
for (int x : pos)
{
fout << x << ' ';
}
fout << '\n';
return 0;
}