Pagini recente » Cod sursa (job #2646591) | Cod sursa (job #2620189) | Cod sursa (job #2477051) | Cod sursa (job #2981792) | Cod sursa (job #2791556)
#include <fstream>
#include <string>
#include <vector>
#define MOD1 1000000009
#define MOD2 1000000007
#define BASE 293
long long int hash11, hash12;
std::vector <long long int> hash21;
std::vector <long long int> hash22;
int ans[1005];
int main() {
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string str1, str2;
int cnt = 0;
long long int put1 = 1, put2 = 1;
fin >> str1 >> str2;
hash21.resize(str2.size() + 1);
hash22.resize(str2.size() + 1);
if (str2.size() < str1.size()) {
fout << "0";
return 0;
}
hash11 = 0;
hash12 = 0;
for (int index = str1.size() - 1; index >= 0; index--) {
hash11 *= BASE;
hash11 += str1[index];
hash11 %= MOD1;
hash12 *= BASE;
hash12 += str1[index];
hash12 %= MOD2;
put1 *= BASE;
put1 %= MOD1;
put2 *= BASE;
put2 %= MOD2;
}
hash21[str2.size()] = 0;
hash22[str2.size()] = 0;
for (int index = str2.size() - 1; index >= 0; index--) {
hash21[index] = hash21[index + 1] * BASE + str2[index];
hash21[index] %= MOD1;
hash22[index] = hash22[index + 1] * BASE + str2[index];
hash22[index] %= MOD2;
}
for (int index = 0; index <= str2.size() - str1.size(); index++) {
if (hash11 == (hash21[index] + MOD1 - (hash21[index + str1.size()] * put1) % MOD1) % MOD1 &&
hash12 == (hash22[index] + MOD2 - (hash22[index + str1.size()] * put2) % MOD2) % MOD2) {
ans[cnt] = index;
cnt++;
}
if (cnt == 1000) {
break;
}
}
fout << cnt << '\n';
for (int index = 0; index < cnt; index++) {
fout << ans[index] << ' ';
}
return 0;
}