Pagini recente » Cod sursa (job #286380) | Cod sursa (job #295650) | Cod sursa (job #156250) | Cod sursa (job #121260) | Cod sursa (job #3156852)
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <fstream>
struct Trie {
private:
constexpr static const int K = 26;
struct Vertex {
std::vector<int> next;
int output = -1;
int fail = -1;
Vertex() {
next.resize(K, -1);
}
};
std::vector<Vertex> tree;
int &next(int node, char c) {
return tree[node].next[c - 'a'];
}
int &output(int node) {
return tree[node].output;
}
int &fail(int node) {
return tree[node].fail;
}
void push_links() {
std::queue<int> queue;
for (char i = 'a'; i <= 'z'; ++i) {
int s = next(0, i);
if (s > 0) {
queue.push(s);
fail(s) = 0;
}
}
while (!queue.empty()) {
int top = queue.front();
queue.pop();
for (char i = 'a'; i <= 'z'; ++i) {
int s = next(top, i);
if (s == -1) continue;
queue.push(s);
int state = fail(top);
while (next(state, i) == -1) state = fail(state);
fail(s) = next(state, i);
}
}
}
public:
Trie() {
tree.emplace_back();
}
void add_word(const std::string &str, int idx) {
int node = 0;
for (auto i: str) {
if (next(node, i) == -1) {
next(node, i) = (int) tree.size();
tree.emplace_back();
}
node = next(node, i);
}
output(node) = idx;
}
void compute() {
fail(0) = 0;
for (char i = 'a'; i <= 'z'; ++i) {
if (next(0, i) == -1) next(0, i) = 0;
}
push_links();
}
void advance(int &state, char c, const std::function<void(int)> &dispatch) {
while (next(state, c) == -1) state = fail(state);
state = next(state, c);
dispatch(output(state));
int cpy = fail(state);
while (cpy != 0) {
dispatch(output(cpy));
cpy = fail(cpy);
}
}
};
struct InputParser {
private:
FILE *file;
int ptr{};
char *buffer;
char read() {
if (ptr == 4096) {
fread(buffer, 1, 4096, file);
ptr = 0;
}
return buffer[ptr++];
}
public:
explicit InputParser(const std::string &file) {
this->file = fopen(file.c_str(), "r");
ptr = 4096;
buffer = new char[4096];
}
inline InputParser &operator>>(char &c) {
c = read();
return *this;
}
inline InputParser &operator>>(std::string &str) {
char c;
while (!std::isalpha(c = read()));
str += c;
while (std::isalpha(c = read())) {
str += c;
}
return *this;
}
inline InputParser &operator>>(int &n) {
char c;
while (!std::isdigit(c = read()));
n = c - '0';
while (std::isdigit(c = read())) n = n * 10 + c - '0';
return *this;
}
};
class OutputParser {
private:
FILE *file;
char *buffer;
int ptr;
void write(char ch) {
if (ptr == 50000) {
fwrite(buffer, 1, 50000, file);
ptr = 0;
}
buffer[ptr++] = ch;
}
public:
explicit OutputParser(const std::string &file) {
this->file = fopen(file.c_str(), "w");
buffer = new char[50000]();
ptr = 0;
}
~OutputParser() {
fwrite(buffer, 1, ptr, file);
fclose(file);
}
inline OutputParser &operator<<(int vu32) {
if (vu32 <= 9) {
write(vu32 + '0');
} else {
(*this) << (vu32 / 10);
write(vu32 % 10 + '0');
}
return *this;
}
inline OutputParser &operator<<(char ch) {
write(ch);
return *this;
}
};
int main() {
InputParser input("ahocorasick.in");
OutputParser output("ahocorasick.out");
Trie trie;
std::string s;
int n;
input >> s >> n;
std::unordered_map<std::string, int> map;
std::vector<std::string> words(n);
for (int i = 0; i < n; ++i) {
input >> words[i];
if (map[words[i]] == 0) map[words[i]] = i + 1;
}
for (const auto &[str, idx]: map) {
trie.add_word(str, idx);
}
std::vector<int> ans(n + 1);
auto dispatch = [&ans](int idx) {
if (idx != -1) ans[idx]++;
};
int state = 0;
trie.compute();
for (char i: s) {
trie.advance(state, i, dispatch);
}
for (int i = 0; i < n; ++i) output << ans[map[words[i]]] << '\n';
return 0;
}