Pagini recente » Cod sursa (job #1002512) | Cod sursa (job #2541818) | Cod sursa (job #1992484) | Cod sursa (job #2645263) | Cod sursa (job #3277931)
#include <bits/stdc++.h>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
const int SIZE = 2e6;
const int base = 269696969;
const int mod = 1e9 + 7;
int64_t text_hash[SIZE + 1], power[SIZE + 1];
std::string pattern, text;
void precompute_powers()
{
power[0] = 1;
for(int i = 1; i <= SIZE; ++i)
power[i] = (power[i - 1] * base) % mod;
}
int main()
{
fin >> pattern >> text;
int text_len = text.length();
int pattern_len = pattern.length();
precompute_powers();
uint64_t pattern_hash = 0;
for(int i = 0; i < pattern_len; ++i)
{
pattern_hash *= base;
pattern_hash += pattern[i] - '0';
pattern_hash %= mod;
}
for(int i = 0; i < text_len; ++i)
{
text_hash[i + 1] = text_hash[i] * base;
text_hash[i + 1] += text[i] - '0';
text_hash[i + 1] %= mod;
}
int count = 0;
std::vector<int> positions;
for(int i = pattern_len; i <= text_len; ++i)
{
int64_t full_hash = text_hash[i];
int64_t old_hash = text_hash[i - pattern_len];
int64_t curr_hash = (full_hash - (old_hash * power[pattern_len]) % mod + mod) % mod;
if(curr_hash == pattern_hash)
{
count++;
if(count <= 1000)
positions.emplace_back(i - pattern_len);
}
}
fout << count << "\n";
for(auto position : positions)
fout << position << " ";
return 0;
}