Pagini recente » Cod sursa (job #2539090) | Cod sursa (job #250707) | Cod sursa (job #286434) | Cod sursa (job #540274) | Cod sursa (job #3233320)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>
using namespace std;
const int ALPHABET_SIZE = 3;
struct TrieNode {
TrieNode* children[ALPHABET_SIZE];
TrieNode* fail;
bool is_end;
TrieNode() : fail(nullptr), is_end(false) {
memset(children, 0, sizeof(children));
}
};
class AhoCorasick {
public:
AhoCorasick() {
root = new TrieNode();
}
~AhoCorasick() {
deleteTrie(root);
}
void insert(const string& word) {
TrieNode* node = root;
for (char ch : word) {
int idx = ch - 'a';
if (!node->children[idx]) {
node->children[idx] = new TrieNode();
}
node = node->children[idx];
}
node->is_end = true;
}
void build() {
queue<TrieNode*> q;
root->fail = root;
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (root->children[i]) {
root->children[i]->fail = root;
q.push(root->children[i]);
}
}
while (!q.empty()) {
TrieNode* current = q.front();
q.pop();
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (current->children[i]) {
TrieNode* child = current->children[i];
TrieNode* fail = current->fail;
while (fail != root && !fail->children[i]) {
fail = fail->fail;
}
if (fail->children[i] && fail->children[i] != child) {
child->fail = fail->children[i];
} else {
child->fail = root;
}
child->is_end = child->is_end || child->fail->is_end;
q.push(child);
}
}
}
}
int search(const string& text) {
TrieNode* node = root;
int count = 0;
for (char ch : text) {
int idx = ch - 'a';
while (node != root && !node->children[idx]) {
node = node->fail;
}
if (node->children[idx]) {
node = node->children[idx];
} else {
node = root;
}
if (node->is_end) {
count++;
}
}
return count;
}
private:
TrieNode* root;
void deleteTrie(TrieNode* node) {
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (node->children[i]) {
deleteTrie(node->children[i]);
}
}
delete node;
}
};
int main() {
ifstream infile("abc2.in");
ofstream outfile("abc2.out");
string text;
infile >> text;
AhoCorasick aho;
string word;
while (infile >> word) {
aho.insert(word);
}
aho.build();
int result = aho.search(text);
outfile << result << endl;
infile.close();
outfile.close();
return 0;
}