Pagini recente » Cod sursa (job #2892847) | Cod sursa (job #2512585) | Cod sursa (job #2949344) | Cod sursa (job #319405) | Cod sursa (job #2791513)
#include <fstream>
#include <string>
#include <vector>
#define MOD 1000000009
#define BASE 293
long long int hash1;
std::vector <long long int> hash2;
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 put = 1;
fin >> str1 >> str2;
hash2.resize(str2.size() + 1);
if (str2.size() < str1.size()) {
fout << "0";
return 0;
}
hash1 = 0;
for (int index = str1.size() - 1; index >= 0; index--) {
hash1 *= BASE;
hash1 += str1[index];
hash1 %= MOD;
put *= BASE;
put %= MOD;
}
hash2[str2.size()] = 0;
for (int index = str2.size() - 1; index >= 0; index--) {
hash2[index] = hash2[index + 1] * BASE + str2[index];
hash2[index] %= MOD;
}
for (int index = 0; index <= str2.size() - str1.size(); index++) {
if (hash1 == (hash2[index] + MOD - (hash2[index + str1.size()] * put) % MOD) % MOD) {
ans[cnt] = index;
cnt++;
}
if (cnt == 1000) {
break;
}
}
fout << cnt << '\n';
for (int index = 0; index < cnt; index++) {
fout << ans[index] << ' ';
}
return 0;
}