Pagini recente » Borderou de evaluare (job #1311704) | Cod sursa (job #2833812) | Cod sursa (job #282981) | Cod sursa (job #1138445) | Cod sursa (job #1416612)
//Problem d from baraj15
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
typedef int var;
#define MAXC 10005
#define MAXL 100005
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
string text;
string cuv;
unordered_map<var, bool> Check;
unordered_map<var, var> hMap;
vector<var> Sol;
var n;
const var SIZE = 2;
const var B[SIZE] = {81724132, 12139831, 3239821, 412379, 223918};
const var BASE = 12837;
var H[SIZE];
void addHash(char val);
void emptyHash();
void Read() {
fin>>text;
fin>>n;
Sol.resize(n);
for(var i=0; i<n; i++) {
fin>>cuv;
emptyHash();
for(auto c : cuv)
addHash(c);
var h = 0;
for(var i=0; i<SIZE; i++)
h = h * BASE + H[i];
cerr << "Hash of " << cuv << ": " << h << '\n';
Check[cuv.size()] = 1;
hMap[h] = i;
}
}
void addHash(char val) {
for(var i=0; i<SIZE; i++) {
H[i] = H[i] * B[i] + val;
}
}
void checkHash() {
var h = 0;
for(var i=0; i<SIZE; i++) {
h = h * BASE + H[i];
}
cerr << "Checking " << h << "\n";
if(hMap.find(h) == hMap.end())
return;
cerr << "Found: " << hMap[h] << '\n';
Sol[hMap[h]] ++;
}
var PUT[SIZE][MAXL], COMP[SIZE][MAXL];
var put(var basei, var e) {
if(COMP[basei][e])
return PUT[basei][e];
if(e == 0) return 1;
PUT[basei][e] = B[basei] * put(basei, e-1);
COMP[basei][e] = 1;
return PUT[basei][e];
}
void subHash(char val, var len) {
for(var i=0; i<SIZE; i++) {
H[i] -= put(i, len) * val;
}
}
void emptyHash() {
for(var i=0; i<SIZE; i++) {
H[i] = 0;
}
}
void Solve(var length) {
emptyHash();
for(var i=0; i<length; i++)
addHash(text[i]);
checkHash();
for(var i=length; i<text.size(); i++) {
addHash(text[i]);
subHash(text[i-length], length);
checkHash();
}
}
int main() {
Read();
for(auto &l : Check) {
Solve(l.first);
}
for(var i=0; i<n; i++) {
fout<<Sol[i]<<'\n';
}
return 0;
}