Pagini recente » Cod sursa (job #2617515) | Cod sursa (job #2138245) | Cod sursa (job #2885633) | Cod sursa (job #3202778) | Cod sursa (job #2886513)
#include <fstream>
#include <vector>
std::ifstream fin ("strmatch.in");
std::ofstream fout ("strmatch.out");
int const p = 73;
int const MOD1 = 1e9 + 21;
int const MOD2 = 1e9 + 7;
std::vector <int> aparitii;
int main() {
std::string s1, s2;
fin >> s1 >> s2;
int n1 = s1.length(),
n2 = s2.length();
int hash1 = 0,
hash2 = 0;
int putere1 = 1,
putere2 = 1;
for (int i = 0; i < n1; i++) {
hash1 = ((hash1 * p) + s1[i] - '0') % MOD1;
hash2 = ((hash2 * p) + s1[i] - '0') % MOD2;
if (i != 0) {
putere1 = (putere1 * p) % MOD1;
putere2 = (putere2 * p) % MOD2;
}
}
int curr1 = 0,
curr2 = 0;
for (int i = 0; i < n1; i++) {
curr1 = ((curr1 * p) + s2[i] - '0') % MOD1;
curr2 = ((curr2 * p) + s2[i] - '0') % MOD2;
}
if (curr1 == hash1 && curr2 == hash2)
aparitii.push_back(0);
for (int i = n1; i < n2; i++) {
curr1 = (curr1 - (s2[i - n1] - '0') * putere1 + MOD1) % MOD1;
curr2 = (curr2 - (s2[i - n1] - '0') * putere2 + MOD2) % MOD2;
curr1 = ((curr1 * p) + s2[i] - '0') % MOD1;
curr2 = ((curr2 * p) + s2[i] - '0') % MOD2;
if (curr1 == hash1 && curr2 == hash2)
aparitii.push_back(i - n1 + 1);
}
int size = aparitii.size();
fout << size << "\n";
size = std::min(size, 1000);
for (int i = 0; i < size; i++)
fout << aparitii[i] << " ";
return 0;
}