Pagini recente » Cod sursa (job #1937161) | Cod sursa (job #1370189) | Cod sursa (job #1925868) | Cod sursa (job #1303119) | Cod sursa (job #2078897)
#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 putere = 1;
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 < 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;
putere = (1LL * putere * BASE ) % MOD;
}
}
int subhash(int st, int dr)
{
int aux = (hash_text[dr] - (1LL * hash_text[st - 1] * putere) % MOD) % MOD;
if (aux < 0)
aux += MOD;
return aux;
}
void read()
{
fin >> pattern >> text;
}
int main()
{
read();
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);
}
cout << ans.size() << '\n';
while (!ans.empty())
{
cout << ans.front() << " ";
ans.pop();
}
return 0;
}