Pagini recente » Cod sursa (job #891150) | Cod sursa (job #3193904) | Cod sursa (job #1391717) | Cod sursa (job #1086610) | Cod sursa (job #3233319)
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <fstream>
#include <cstring>
using namespace std;
struct TrieNode {
unordered_map<char, TrieNode*> children;
TrieNode* fail;
bool is_end;
TrieNode() : fail(nullptr), is_end(false) {}
};
class AhoCorasick {
public:
AhoCorasick() {
root = new TrieNode();
}
~AhoCorasick() {
deleteTrie(root);
}
void insert(const string& word) {
TrieNode* node = root;
for (char ch : word) {
if (node->children.find(ch) == node->children.end()) {
node->children[ch] = new TrieNode();
}
node = node->children[ch];
}
node->is_end = true;
}
void build() {
queue<TrieNode*> q;
root->fail = root;
for (auto& pair : root->children) {
pair.second->fail = root;
q.push(pair.second);
}
while (!q.empty()) {
TrieNode* current = q.front();
q.pop();
for (auto& pair : current->children) {
char ch = pair.first;
TrieNode* child = pair.second;
TrieNode* fail = current->fail;
while (fail != root && fail->children.find(ch) == fail->children.end()) {
fail = fail->fail;
}
if (fail->children.find(ch) != fail->children.end()) {
child->fail = fail->children[ch];
} 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) {
while (node != root && node->children.find(ch) == node->children.end()) {
node = node->fail;
}
if (node->children.find(ch) != node->children.end()) {
node = node->children[ch];
} else {
node = root;
}
TrieNode* temp = node;
while (temp != root) {
if (temp->is_end) {
count++;
break;
}
temp = temp->fail;
}
}
return count;
}
private:
TrieNode* root;
void deleteTrie(TrieNode* node) {
for (auto& pair : node->children) {
deleteTrie(pair.second);
}
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;
}