Pagini recente » Cod sursa (job #2812589) | Cod sursa (job #1896029) | Cod sursa (job #2173622) | Cod sursa (job #1456628) | Cod sursa (job #3233318)
#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;
vector<int> output;
TrieNode() : fail(nullptr) {}
};
class AhoCorasick {
public:
AhoCorasick() {
root = new TrieNode();
}
void insert(const string& word, int index) {
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->output.push_back(index);
}
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->output.insert(child->output.end(), child->fail->output.begin(), child->fail->output.end());
q.push(child);
}
}
}
int search(const string& text, int wordCount) {
TrieNode* node = root;
vector<int> found(text.length(), 0);
for (size_t i = 0; i < text.length(); ++i) {
char ch = text[i];
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;
}
for (int index : node->output) {
found[i]++;
}
}
int candidatePositions = 0;
for (size_t i = 0; i <= text.length() - wordLength; ++i) {
if (found[i] > 0) {
candidatePositions++;
}
}
return candidatePositions;
}
void setWordLength(int length) {
wordLength = length;
}
private:
TrieNode* root;
int wordLength;
};
int main() {
ifstream infile("abc2.in");
ofstream outfile("abc2.out");
string text;
infile >> text;
AhoCorasick aho;
int wordCount = 0;
int wordLength = 0;
string word;
while (infile >> word) {
aho.insert(word, wordCount++);
wordLength = word.length();
}
aho.build();
aho.setWordLength(wordLength);
int result = aho.search(text, wordCount);
outfile << result << endl;
infile.close();
outfile.close();
return 0;
}