Determining DNA Health

  • + 0 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();
    }