Pagini recente » Cod sursa (job #640407) | lot_warmup_22_1 | Borderou de evaluare (job #1174787) | Borderou de evaluare (job #2134734) | Cod sursa (job #2078916)
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int BASE1 = 73;
const int BASE2 = 79;
const int MOD1 = 666013;
const int MOD2 = 1000000007;
const int NMAX = 2000000 + 5;
queue <int> ans;
string pattern, text;
int hash_text1, hash_pattern1;
int hash_text2, hash_pattern2;
int encrypt(char x)
{
if (isdigit(x))
return x;
if ('a' <= x && x <= 'z')
return 10 + x - 'a';
return 36 + x - 'A';
}
void init_hash()
{
for (int i = 0; i < pattern.size(); ++i)
hash_pattern1 = (1LL * hash_pattern1 * BASE1 + encrypt(pattern[i])) % MOD1;
for (int i = 0; i < pattern.size(); ++i)
hash_pattern2 = (1LL * hash_pattern2 * BASE2 + encrypt(pattern[i])) % MOD2;
}
void read()
{
fin >> pattern >> text;
}
int main()
{
read();
init_hash();
int cnt = 0, put1 = 1, put2 = 1;
for (int i = 0; i < pattern.size(); i++)
{
put1 = (1LL * put1 * BASE1) % MOD1;
put2 = (1LL * put2 * BASE2) % MOD2;
}
for (int i = 0; i < text.size(); ++i)
{
hash_text1 = (1LL * hash_text1 * BASE1 + encrypt(text[i])) % MOD1;
hash_text2 = (1LL * hash_text2 * BASE2 + encrypt(text[i])) % MOD2;
if (i >= pattern.size())
{
hash_text1 -= (1LL * encrypt(text[i - pattern.size()]) * put1) % MOD1;
hash_text2 -= (1LL * encrypt(text[i - pattern.size()]) * put2) % MOD2;
}
if (hash_text1 < 0) hash_text1 += MOD1;
if (hash_text2 < 0) hash_text2 += MOD2;
if (i >= pattern.size() - 1 && hash_pattern1 == hash_text1 && hash_pattern2 == hash_text2)
{
++cnt;
if (cnt <= 1000) ans.push(i - pattern.size() + 1);
}
}
fout << cnt << '\n';
while (!ans.empty())
{
fout << ans.front() << " ";
ans.pop();
}
return 0;
}