Pagini recente » Cod sursa (job #2232346) | Cod sursa (job #1309124) | Cod sursa (job #660175) | Cod sursa (job #725465) | Cod sursa (job #3293411)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int p = 73;
const ll m = 1e9 + 9;
vector<ll> p_pow;
string pattern, str;
int pattern_size, str_size;
void compute_powers()
{
ll pp = 1;
for(int i=0; i<=str_size; i++)
{
p_pow.push_back(pp);
pp = (pp*p) % m;
}
}
ll compute_hash(string s)
{
ll hash_val = 0;
for(int i=0; i<s.size(); i++)
hash_val = (hash_val + (s[i]-'0'+1) * p_pow[i]) % m;
return hash_val;
}
int main()
{
fin >> pattern >> str;
pattern_size = pattern.size();
str_size = str.size();
compute_powers();
ll pattern_hash = 0;
for(int i=0; i<pattern_size; i++)
pattern_hash = (pattern_hash + (pattern[i] - '0' + 1)*p_pow[i]) % m;
vector<ll> pref_hash(str_size+1, 0);
for(int i=0; i<str_size; i++)
{
pref_hash[i+1] = (pref_hash[i] + (str[i] - '0' + 1) * p_pow[i]) % m;
}
vector<int> occurences;
for(int i=0; i<str_size - pattern_size+1; i++)
{
ll curr_hash = (pref_hash[i + pattern_size] + m - pref_hash[i]) % m;
if(curr_hash == pattern_hash * p_pow[i] % m)
occurences.push_back(i);
}
fout<<occurences.size()<<'\n';
int size = occurences.size();
if(size > 1000)
size = 1000;
for(int i=0; i<size; i++)
fout<<occurences[i]<<' ';
return 0;
}