You are viewing a single comment's thread. Return to all comments →
wow this actually works
aho corasick
class Node { public: char letter = '\0'; Node* suffix = NULL; Node* suffixWord = NULL; Node* children[26] = { NULL }; vector<int> index; Node(char c) : letter(c) {} }; class trie { public: Node* root = new Node('\0'); void insert(const string& s, int index) { Node* T = root; for (char c : s) { if (T->children[c - 'a'] == NULL) T->children[c - 'a'] = new Node(c); T = T->children[c - 'a']; } T->index.push_back(index); } }; void trieBuilder(const vector<string>& dictionary, trie& Trie) { for (int i = 0; i < dictionary.size(); ++i) Trie.insert(dictionary[i], i); Trie.root->suffix = Trie.root; queue<Node*> Q; Q.push(Trie.root); while (!Q.empty()) { for (Node* child : Q.front()->children) { if (child == NULL) continue; int c = child->letter - 'a'; Node* temp = Q.front()->suffix; while (temp != Trie.root and temp->children[c] == NULL) temp = temp->suffix; if (temp->children[c] != NULL and temp->children[c] != child) child->suffix = temp->children[c]; else child->suffix = Trie.root; child->suffixWord = (!child->suffix->index.empty()) ? child->suffix : child->suffix->suffixWord; Q.push(child); } Q.pop(); } } void finder(const trie& Trie, const string& text, const vector<long>& health, long& total, int start, int end) { Node* current = Trie.root; for (int i = 0; i < text.size(); ++i) { int c = text[i] - 'a'; while (current != Trie.root and current->children[c] == NULL) current = current->suffix; if (current->children[c] != NULL) current = current->children[c]; Node* temp = current; while (temp != NULL) { for (int index : temp->index) { if (index >= start and index <= end) total = total + health[index]; } temp = temp->suffixWord; } } } int main() { int n, s, k, start, end; string temp, d; vector<string> genes; vector<long> health, totalHealth; trie Trie; cin >> n; for (int i = 1; i <= n; ++i) { cin >> temp; genes.push_back(temp); } for (int i = 1; i <= n; ++i) { cin >> k; health.push_back(k); } trieBuilder(genes, Trie); cin >> s; for (int i = 1; i <= s; ++i) { long total = 0; cin >> start >> end >> d; finder(Trie, d, health, total, start, end); totalHealth.push_back(total); } sort(totalHealth.begin(), totalHealth.end()); cout << totalHealth[0] << ' ' << totalHealth.back(); }
Seems like cookies are disabled on this browser, please enable them to open this website
Determining DNA Health
You are viewing a single comment's thread. Return to all comments →
wow this actually works
aho corasick