Pagini recente » Cod sursa (job #744730) | Cod sursa (job #71020) | Cod sursa (job #1191260) | Cod sursa (job #2029088) | Cod sursa (job #2078898)
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int BASE = 71;
const int MOD = 666013;
const int NMAX = 2000000 + 5;
queue <int> ans;
string pattern, text;
int hash_text[NMAX], hash_pattern;
int bases[NMAX];
int encrypt(char x)
{
if (isdigit(x))
return x;
if ('a' <= x && x <= 'z')
return 10 + x - 'a';
return 36 + x - 'A';
}
void init_base()
{
bases[0] = 1;
for (int i = 1; i < NMAX; ++i)
bases[i] = (1LL * bases[i - 1] * BASE) % MOD;
}
void init_hash()
{
for (int i = 0; i < text.size(); ++i)
hash_text[i + 1] = (1LL * hash_text[i] * BASE + encrypt(text[i])) % MOD;
for (int i = 0; i < pattern.size(); ++i)
hash_pattern = (1LL * hash_pattern * BASE + encrypt(pattern[i])) % MOD;
}
int subhash(int st, int dr)
{
int aux = (hash_text[dr] - (1LL * hash_text[st - 1] * bases[dr - st + 1]) % MOD) % MOD;
if (aux < 0)
aux += MOD;
return aux;
}
void read()
{
fin >> pattern >> text;
}
int main()
{
read();
init_base();
init_hash();
int cnt = 0;
for (int i = 0; i < text.size() - pattern.size(); ++i)
if (hash_pattern == subhash(i + 1, i + pattern.size()))
{
++cnt;
if (cnt <= 1000) ans.push(i);
}
fout << ans.size() << '\n';
while (!ans.empty())
{
fout << ans.front() << " ";
ans.pop();
}
return 0;
}