Pagini recente » Cod sursa (job #2321321) | Cod sursa (job #848115) | Cod sursa (job #2130396) | Cod sursa (job #532420) | Cod sursa (job #3141818)
#include <fstream>
using namespace std;
ifstream fin("probleme.in");
ofstream fout("probleme.out");
int lgpow(int b, int e, int mod){
int p = 1;
while(e){
if(e & 1)
p = (long long) p * b % mod;
b = (long long) b * b % mod;
e >>= 1;
}
return p;
}
struct Hash{
int value, mod, base, base_power;
void init(int _mod, int _base, int pattern_length){
value = 0;
mod = _mod;
base = _base;
base_power = lgpow(base, pattern_length - 1, mod);
}
void add(char ch){
value = ((long long) value * base % mod + ch - 'A');
if(value >= mod)
value -= mod;
}
void remove(char ch){
value = value - ((long long) (ch - 'A') * base_power % mod);
if(value < 0)
value += mod;
}
int compute(char *s, int slen){
int val = 0;
for(int i = 0; i < slen; ++i){
val = ((long long) val * base % mod + s[i] - 'A');
if(val >= mod)
val -= mod;
}
return val;
}
};
const int STRLEN_MAX = 2e6;
const int APP_MAX = 1e3;
char s[STRLEN_MAX + 1], pattern[STRLEN_MAX + 1];
int v[APP_MAX];
int length(char *s){
int len = 0;
while(s[len]) ++len;
return len;
}
int GetApparitions(char *s, char *pattern){
int ret = 0;
const int len = length(pattern);
const int HASHES = 3;
const int BASE = 256;
const int mod[] = {(int) 1e9 + 7, (int) 1e9 + 9, (int) 1e9 + 21};
Hash h[HASHES];
for(int i = 0; i < HASHES; ++i)
h[i].init(mod[i], BASE, len);
int pattern_hash[HASHES];
for(int i = 0; i < HASHES; ++i){
pattern_hash[i] = h[i].compute(pattern, len);
h[i].value = h[i].compute(s, len - 1);
}
int j = len - 1;
while(s[j]){
int found = 0;
for(int i = 0; i < HASHES; ++i){
h[i].add(s[j]);
if(h[i].value == pattern_hash[i])
++found;
h[i].remove(s[j - len + 1]);
}
if(found == HASHES)
v[ret++] = j - len + 1;
++j;
}
return ret;
}
int main(){
fin >> pattern >> s;
int apparitons = GetApparitions(s, pattern);
fout << apparitons << '\n';
for(int i = 0; i < apparitons; ++i)
fout << v[i] << ' ';
fout.put('\n');
fin.close();
fout.close();
return 0;
}