HackerRank Count Strings problem solution

In this HackerRank Count Strings problem solution, we have given a regular expression and an the length L. we need to count how many strings of length L are recognized by it.

Problem solution in Python.

from enum import Enum
from collections import namedtuple

Edge = namedtuple('Edge', 'dest char')

class Alphabet(Enum):
    a = 'a'
    b = 'b'
    e = None


def empty_edge(dest):
    return Edge(dest, Alphabet.e)


class CountStrings:
    def __init__(self, regex_string):
        RegexGraphNFA.node_count = 0
        self.regex_string = regex_string
        nfa_graph = self.translate_regex()
        translate_graph = TranslateGraph(nfa_graph)
        self.dfa_graph = translate_graph.translate()

    def calculate(self, string_length):
        return self.dfa_graph.count_paths(string_length)

    def translate_regex(self, index=0):
        result_set = ResultSet()
        while index < len(self.regex_string):
            if self.regex_string[index] == '(':
                out_list, index = self.translate_regex(index + 1)
                result_set.insert(out_list)
            elif self.regex_string[index] == ')':
                result = result_set.calculate_result()
                return result, index
            elif self.regex_string[index] == '|':
                result_set.set_or()
            elif self.regex_string[index] == '*':
                result_set.set_repeat()
            else:
                result_set.insert(RegexGraphNFA(Alphabet[self.regex_string[index]]))
            index += 1
        return result_set.calculate_result()


class ResultSet:
    AND, OR, REPEAT = 1, 2, 3

    def __init__(self):
        self.r1 = None
        self.r2 = None
        self.op = self.AND

    def set_or(self):
        self.op = self.OR

    def set_repeat(self):
        self.op = self.REPEAT

    def calculate_result(self):
        if self.op == self.REPEAT:
            self.calculate_repeat()
        elif self.r2 is None:
            pass
        elif self.op == self.OR:
            self.calculate_or()
        else:
            self.calculate_and()
        return self.r1

    def calculate_repeat(self):
        self.r1.graph_repeat()

    def calculate_or(self):
        self.r1.graph_or(self.r2)

    def calculate_and(self):
        self.r1.graph_add(self.r2)

    def insert(self, value):
        if self.r1 is None:
            self.r1 = value
        else:
            self.r2 = value


class RegexGraphNFA:
    node_count = 0

    def __init__(self, in_char):
        self.edges = None
        self.head = None
        self.tail = None
        self.insert_char(in_char)

    @classmethod
    def get_next_node_id(cls):
        node_id = cls.node_count
        cls.node_count += 1
        return node_id

    def insert_char(self, value):
        self.head = self.get_next_node_id()
        self.tail = self.get_next_node_id()
        self.edges = {self.head: [Edge(self.tail, value)],
                      self.tail: []}

    def graph_add(self, other):
        join_node = self.get_next_node_id()
        self.join(other)
        self.edges[self.tail].append(empty_edge(join_node))
        self.edges[join_node] = [empty_edge(other.head)]
        self.tail = other.tail

    def graph_repeat(self):
        new_head = self.get_next_node_id()
        new_tail = self.get_next_node_id()
        self.edges[self.tail].extend([empty_edge(self.head), empty_edge(new_tail)])
        self.edges[new_head] = [empty_edge(self.head), empty_edge(new_tail)]
        self.edges[new_tail] = []
        self.head = new_head
        self.tail = new_tail

    def graph_or(self, other):
        new_head = self.get_next_node_id()
        new_tail = self.get_next_node_id()
        self.join(other)
        self.edges[new_head] = [empty_edge(self.head), empty_edge(other.head)]
        self.edges[self.tail].append(empty_edge(new_tail))
        self.edges[other.tail].append(empty_edge(new_tail))
        self.edges[new_tail] = []
        self.head = new_head
        self.tail = new_tail

    def join(self, other):
        for node, edge in other.edges.items():
            if node in self.edges:
                self.edges[node].extend(edge)
            else:
                self.edges[node] = edge

    def get_dfa_char_node_set(self, origin, use_char):
        node_set = set()
        for my_node in origin:
            for edges in self.edges[my_node]:
                if edges.char == use_char:
                    node_set.add(edges.dest)

        return self.get_dfa_zero_node_set(node_set)

    def get_dfa_zero_node_set(self, origin):
        node_set = set(origin)
        processed = set()
        while len(node_set.difference(processed)) > 0:
            my_node = node_set.difference(processed).pop()
            for edges in self.edges[my_node]:
                if edges.char == Alphabet.e:
                    node_set.add(edges.dest)
            processed.add(my_node)
        return frozenset(node_set)


class TranslateGraph:
    language = (Alphabet.a, Alphabet.b)

    def __init__(self, nfa_graph: RegexGraphNFA):
        self.node_count = 0
        self.nfa_graph = nfa_graph
        self.trans_to = {}
        self.trans_from = {}
        self.table = {}

    def get_next_node_id(self):
        node_id = self.node_count
        self.node_count += 1
        return node_id

    def add_translate(self, nfa_ids):
        if len(nfa_ids) == 0:
            return None
        if nfa_ids not in self.trans_from:
            dfa_id = self.get_next_node_id()
            self.trans_to[dfa_id] = nfa_ids
            self.trans_from[nfa_ids] = dfa_id
            self.table[dfa_id] = dict(zip(self.language, [None] * len(self.language)))
        return self.trans_from[nfa_ids]

    def translate(self):
        self.create_translate_table()
        return self.build_dfa()

    def build_dfa(self):
        head = 0
        valid_ends = set()
        adjacency = {}
        for node, edges in self.table.items():
            adjacency[node] = []
            if self.nfa_graph.tail in self.trans_to[node]:
                valid_ends.add(node)
            for my_char, node_dest in edges.items():
                if node_dest is not None:
                    adjacency[node].append(Edge(node_dest, my_char))
        return RegexGraphDFA(head, valid_ends, adjacency)

    def create_translate_table(self):
        nfa_ids = self.nfa_graph.get_dfa_zero_node_set({self.nfa_graph.head})
        self.add_translate(nfa_ids)
        processed = set()

        while len(set(self.table).difference(processed)) > 0:
            my_node = set(self.table).difference(processed).pop()
            for char in self.language:
                next_nodes = self.nfa_graph.get_dfa_char_node_set(self.trans_to[my_node], char)
                dfa_id = self.add_translate(next_nodes)
                self.table[my_node][char] = dfa_id
            processed.add(my_node)


class RegexGraphDFA:
    def __init__(self, head, valid_ends, edges):
        self.edges = edges
        self.head = head
        self.valid_ends = valid_ends
        self.edge_matrix = Matrix.get_from_edges(len(self.edges), self.edges)

    def count_paths(self, length):
        modulo = 1000000007
        if length == 0:
            return 0 if 0 not in self.valid_ends else 1
        edge_walk = self.edge_matrix.pow(length, modulo)
        count = 0
        for end_node in self.valid_ends:
            count += edge_walk.matrix[self.head][end_node]
        return count % modulo


class Matrix:
    @staticmethod
    def get_from_edges(dimension, adj_list):
        my_matrix = Matrix.get_zeros(dimension)
        my_matrix.add_edges(adj_list)
        return my_matrix

    @staticmethod
    def get_zeros(dimension):
        my_matrix = Matrix(dimension)
        my_matrix.pad_zeros()
        return my_matrix

    def copy(self):
        my_matrix = Matrix(self.dimension)
        my_matrix.matrix = []
        for i in range(self.dimension):
            my_matrix.matrix.append([])
            for j in range(self.dimension):
                my_matrix.matrix[i].append(self.matrix[i][j])
        return my_matrix

    def __init__(self, dimension):
        self.matrix = None
        self.dimension = dimension

    def __str__(self):
        my_str = ''
        for row in self.matrix:
            my_str += str(row) + "n"
        return my_str

    def pad_zeros(self):
        self.matrix = []
        for i in range(self.dimension):
            self.matrix.append([])
            for j in range(self.dimension):
                self.matrix[i].append(0)

    def add_edges(self, adj_list):
        if adj_list is not None:
            for from_node, edge_list in adj_list.items():
                for to_node, my_char in edge_list:
                    self.matrix[from_node][to_node] = 1

    def pow(self, pow_val, mod_val=None):
        started = False
        current_pow = 1
        current_val = 0
        while pow_val > 0:
            if current_pow == 1:
                current_pow_matrix = self.copy()
            else:
                current_pow_matrix = current_pow_matrix.mat_square_mult(current_pow_matrix, mod_val)
            if pow_val % (2 * current_pow):
                current_val += current_pow
                if started:
                    result = result.mat_square_mult(current_pow_matrix, mod_val)
                else:
                    result = current_pow_matrix.copy()
                    started = True
                pow_val -= current_pow
            current_pow *= 2
        return result

    def mat_square_mult(self, other, mod_val=None):
        result = Matrix.get_zeros(self.dimension)
        for i in range(self.dimension):
            for j in range(self.dimension):
                val = 0
                for k in range(self.dimension):
                    val += self.matrix[i][k] * other.matrix[k][j]
                if mod_val is not None:
                    val %= mod_val
                result.matrix[i][j] = val

        return result


def main():
    cases = int(input().strip())
    for i in range(cases):
        in_line = input().strip().split()
        my_class = CountStrings(in_line[0])
        print(my_class.calculate(int(in_line[1])))


if __name__ == "__main__":
    main()

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

class Regex {
        static char e = '';

        final Node root;
        final Node[] nodes;

        Regex(String regex) {
            Parser parser = new Parser(regex);
            parser.parse();
            SubsetConstruction subset = new SubsetConstruction(parser.expr.start, parser.expr.end);
            this.nodes = subset.dfa();
            this.root = nodes[0];
        }

        class SubsetConstruction {
            private final Node nfaEnd;
            private final Queue<State> queue;
            private final Map<Set<Node>, Node> dfaMap;
            private final Node dfaRoot;

            SubsetConstruction(Node nfaRoot, Node nfaEnd) {
                this.nfaEnd = nfaEnd;
                this.queue = new ArrayDeque<>();
                this.dfaMap = new HashMap<>();
                this.dfaRoot = addState(eClosure(nfaRoot)).dfa;
            }

            Node[] dfa() {
                while (!queue.isEmpty()) {
                    State state = queue.poll();
                    for (char c : new char[]{'a', 'b'}) {
                        Set<Node> nfaNext = eClosure(next(state.nfa, c));
                        if (nfaNext.isEmpty())
                            continue;
                        Node dfaNext = dfaMap.get(nfaNext);
                        if (dfaNext == null)
                            dfaNext = addState(nfaNext).dfa;
                        state.dfa.edges.add(new Edge(c, dfaNext));
                    }
                }
                return getNodes();
            }

            private Node[] getNodes() {
                ArrayList<Node> nodes = new ArrayList<>();
                nodes.add(dfaRoot);
                for (Node node : dfaMap.values())
                    if (node != dfaRoot) nodes.add(node);
                return nodes.toArray(new Node[nodes.size()]);
            }

            private State addState(Set<Node> nfa) {
                State state = new State(nfa);
                state.dfa.isFinal = nfa.contains(nfaEnd);
                dfaMap.put(state.nfa, state.dfa);
                queue.add(state);
                return state;
            }

            class State {
                final Set<Node> nfa;
                final Node dfa = new Node();
                State(Set<Node> nfa) { this.nfa = nfa; }
            }

            private Set<Node> eClosure(Node node) {
                return eClosure(Collections.singletonList(node));
            }

            private Set<Node> eClosure(Collection<Node> nodes) {
                Set<Node> closure = new HashSet<>();
                Stack<Node> stack = new Stack<>();
                stack.addAll(nodes);
                while (!stack.isEmpty()) {
                    Node node = stack.pop();
                    if (closure.add(node))
                        stack.addAll(next(node, e));
                }
                return closure;
            }

            private Collection<Node> next(Collection<Node> nodes, char c) {
                Collection<Node> list = new ArrayList<>();
                for (Node node : nodes)
                    list.addAll(next(node, c));
                return list;
            }

            private Collection<Node> next(Node node, char c) {
                Collection<Node> list = new ArrayList<>();
                for (Edge edge : node.edges)
                    if (edge.value == c) list.add(edge.node);
                return list;
            }
        }

        class Parser {
            private final String regex;
            private int pos;
            Expression expr;

            Parser(String regex) {
                this.regex = regex;
                this.pos = 0;
            }

            Node parse() {
                return (expr = sequence()).start;
            }

            class Expression {
                Node start = new Node();
                Node end = start;
            }

            private Expression sequence() {
                Expression expr = new Expression();
                for (; ; ) {
                    char c = take();
                    switch (c) {
                        case 'a':
                        case 'b': literal(expr, c); break;
                        case '(': expr = parenthesis(expr); break;
                        case '|': expr = pipe(expr); break;
                        case '*': expr = star(expr); break;
                        default: putback(); return expr;
                    }
                }
            }

            private void literal(Expression expr, char c) {
                expr.end.edges.add(new Edge(c, expr.end = new Node()));
            }

            private Expression parenthesis(Expression expr) {
                Expression nested = sequence();
                if (take() != ')')
                    throw new IllegalStateException("syntax error: " + ") expected");
                if (expr.start == expr.end) return nested;
                expr.end.edges.add(new Edge(e, nested.start));
                expr.end = nested.end;
                return expr;
            }

            private Expression pipe(Expression first) {
                Expression second = sequence();
                Expression expr = new Expression();
                expr.start.edges.add(new Edge(e, first.start));
                expr.start.edges.add(new Edge(e, second.start));
                first.end.edges.add(new Edge(e, expr.end = new Node()));
                second.end.edges.add(new Edge(e, expr.end));
                return expr;
            }

            private Expression star(Expression inner) {
                Expression expr = new Expression();
                expr.start.edges.add(new Edge(e, inner.start));
                inner.end.edges.add(new Edge(e, inner.start));
                inner.end.edges.add(new Edge(e, expr.end = new Node()));
                expr.start.edges.add(new Edge(e, expr.end));
                return expr;
            }

            private char take() {
                return skipWs() ? regex.charAt(pos++) : e;
            }

            private void putback() {
                if (pos >= 0) --pos;
            }

            private boolean skipWs() {
                while (pos < regex.length() && Character.isWhitespace(regex.charAt(pos))) ++pos;
                return pos < regex.length();
            }
        }

        class Node {
            final ArrayList<Edge> edges = new ArrayList<>();
            boolean isFinal;
        }

        class Edge {
            final char value;
            final Node node;

            Edge(char value, Node node) {
                this.value = value;
                this.node = node;
            }
        }
    }

    class RegexCounter {
        private final long[][] adjacencyMatrix;
        private final ArrayList<Integer> finalStates;

        RegexCounter(Regex regex) {
            Map<Regex.Node, Integer> indexes = new HashMap<>();
            this.adjacencyMatrix = new long[regex.nodes.length][regex.nodes.length];
            this.finalStates = new ArrayList<>();
            for (Regex.Node node : regex.nodes) {
                int index = getIndex(indexes, node);
                for (Regex.Edge edge : node.edges) {
                    int next = getIndex(indexes, edge.node);
                    adjacencyMatrix[index][next] = 1;
                }
            }
        }

        private int getIndex(Map<Regex.Node, Integer> indexes, Regex.Node node) {
            Integer index = indexes.get(node);
            if (index == null) {
                indexes.put(node, index = indexes.size());
                if (node.isFinal)
                    finalStates.add(index);
            }
            return index;
        }

        long count(int len) {
            long[][] m = new MatrixPower(adjacencyMatrix).power(len);
            long count = 0;
            for (int finalState : finalStates)
                count = (count + m[0][finalState]) % 1000000007L;
            return count;
        }
    }

    class MatrixPower {
        private final long[][] matrix;
        private final Map<Integer, long[][]> powers;

        MatrixPower(long[][] matrix) {
            this.matrix = matrix;
            this.powers = new HashMap<>();
        }

        long[][] power(int p) {
            if (p == 1) return matrix;
            long[][] result = powers.get(p);
            if (result != null)
                return result;
            result = power(p / 2);
            powers.put(p / 2 * 2, result = multiply(result, result));
            if (p % 2 > 0)
                powers.put(p, result = multiply(result, power(p % 2)));
            return result;
        }

        private long[][] multiply(long[][] a, long[][] b) {
            long[][] m = new long[a.length][a.length];
            for (int i = 0; i < a.length; ++i) {
                for (int j = 0; j < a.length; ++j) {
                    long sum = 0;
                    for (int k = 0; k < a.length; ++k)
                        sum = (sum + a[i][k] * b[k][j]) % 1000000007L;
                    m[i][j] = sum;
                }
            }
            return m;
        }
    }
public class Solution {
    
    /*
     * Complete the countStrings function below.
     */
    static long countStrings(String r, int l) {
        return l == 0 ? 0 : new RegexCounter(new Regex(r)).count(l);
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            String[] rl = scanner.nextLine().split(" ");

            String r = rl[0];

            int l = Integer.parseInt(rl[1].trim());

            long result = countStrings(r, l);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

Problem solution in C++.

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <unordered_set>
using namespace std;

long MM = 1000000007;

class Node;

class Edge{
public:
    Node* next;
    char c;
    Edge(Node* next, char c){
        this->next = next;
        this->c = c;
    }
};

class Node{
public:
    vector<Edge*> edges;
};

class DNode{
public:
    int id;
    string str;
    set<int> nodes;
    bool end;
    DNode* a;
    DNode* b;
    DNode(int id, string str, set<int> nodes, bool end = false){
        this->id = id;
        this->str = str;
        this->nodes = nodes;
        this->end = end;
        a = 0; b = 0;
    }
};

class TreeNode{
public:
    int type; // 0-a, 1-b, 2-concat, 3-union, 4-*
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
    TreeNode(TreeNode* parent, int type = 2){
        this->parent = parent;
        this->type = type;
        this->left = 0;
        this->right = 0;
    }
};

TreeNode* makeTree(string s){
    TreeNode* root = new TreeNode(0);
    TreeNode* curr = root;
    bool haveLeft = false;
    for (int i = 0; i < s.size(); i++){
        switch(s[i]){
            case 'a':
            case 'b':{
                if (curr->left) curr->right = new TreeNode(curr, s[i]-'a');
                else curr->left = new TreeNode(curr, s[i]-'a');
                break;
            }
            case '(':{
                TreeNode* tn = new TreeNode(curr);
                if (curr->left) curr->right = tn;
                else curr->left = tn;
                curr = tn;
                break;
            }
            case ')':{
                curr = curr->parent;
                break;
            }
            case '|':{
                curr->type = 3;
                break;
            }
            case '*':{
                curr->type = 4;
                break;
            }
        }
    }
    return root->left;
}

vector<Node*> makeNFA(TreeNode* root){
    vector<Node*> out;
    switch (root->type){
        case 0:
        case 1:{
            out.push_back(new Node());
            out.push_back(new Node());
            out[0]->edges.push_back(new Edge(out[1], 'a' + root->type));
            break;
        }
        case 2:{ // concat
            vector<Node*> p1 = makeNFA(root->left);
            vector<Node*> p2 = makeNFA(root->right);
            bool rec = false;
            for (int i = 1; i < p2.size(); i++){
                if (p2[0] == p2[i]){
                    rec = true;
                    break;
                }
            }
            out = p2;
            out[0] = p1[0];
            for (int i = 1; i < p1.size(); i++){
                p1[i]->edges.insert(p1[i]->edges.end(), p2[0]->edges.begin(), p2[0]->edges.end());
                if (rec) out.push_back(p1[i]);
            }
            break;
        }
        case 3:{ // union
            vector<Node*> p1 = makeNFA(root->left);
            vector<Node*> p2 = makeNFA(root->right);
            out = p1;
            out[0]->edges.insert(out[0]->edges.end(), p2[0]->edges.begin(), p2[0]->edges.end());
            for (int i = 1; i < p2.size(); i++){
                if (p2[i] == p2[0]){
                    p2[i] = p1[0];
                } else {
                    for (int j = 0; j < p2[i]->edges.size(); j++){
                        if (p2[i]->edges[j]->next == p2[0]) p2[i]->edges[j]->next = p1[0];
                    }
                }
            }
            out.insert(out.end(), p2.begin() + 1, p2.end());
            break;
        }
        case 4:{ // *
            out = makeNFA(root->left);
            bool rec = false;
            for (int i = 1; i < out.size(); i++){
                if (out[0] == out[i]) rec = true;
                unordered_set<Edge*> s;
                for (Edge* x : out[i]->edges) s.insert(x);
                for (Edge* x : out[0]->edges) s.insert(x);
                out[i]->edges.assign(s.begin(), s.end());
            }
            if (!rec) out.push_back(out[0]);
            break;
        }
    }
    
    return out;
}

void printTree(TreeNode* root){
    switch(root->type){
        case 0: {cout << 'a'; break;}
        case 1: {cout << 'b'; break;}
        case 2: {
            cout << '(';
            printTree(root->left);
            printTree(root->right);
            cout << ')';
            break;
        }
        case 3:{
            cout << '(';
            printTree(root->left);
            cout << '|';
            printTree(root->right);
            cout << ')';
            break;
        }
        case 4:{
            cout << '(';
            printTree(root->left);
            cout << "*)";
            break;
        }
    }
}

void printNFA(vector<Node*> &v){
    Node* root = v[0];
    map<Node*, int> seen;
    queue<Node*> Q;
    Q.push(root);
    seen[root] = 1;
    while (!Q.empty()){
        Node* n = Q.front();
        Q.pop();
        for (int i = 1; i < v.size(); i++){
            if (v[i] == n) {
                cout << "End ";
                break;
            }
        }
        cout << "Node " << n << ": ";
        for (vector<Edge*>::iterator it = n->edges.begin(); it != n->edges.end(); it++){
            Edge* e = *it;
            cout << e->next << "-" << e->c << " / ";
            if (seen.find(e->next) == seen.end()) {
                seen[e->next] = 1;
                Q.push(e->next);
            }
        }
        cout << endl;
    }
    cout << endl;
}

int countNodes(Node* root){
    map<Node*, int> seen;
    queue<Node*> Q;
    Q.push(root);
    int out = 0;
    while (!Q.empty()){
        Node* n = Q.front();
        Q.pop();
        seen[n] = 1;
        out += 1;
        for (vector<Edge*>::iterator it = n->edges.begin(); it != n->edges.end(); it++){
            Edge* e = *it;
            if (seen.find(e->next) == seen.end()) Q.push(e->next);
        }
    }
    return out;
}

string setString(set<int> &s){
    stringstream ss;
    bool first = true;
    for (set<int>::iterator it = s.begin(); it != s.end(); it++){
        if (!first) ss << " ";
        first = false;
        ss << *it;
    }
    return ss.str();
}

pair<DNode*, int> makeDFA(vector<Node*> &v){
    map<Node*, int> endNodes;
    map<int, Node*> idToNode;
    map<Node*, int> nodeToId;
    queue<Node*> Q1;
    Q1.push(v[0]);
    idToNode[0] = v[0];
    nodeToId[v[0]] = 0;
    int nextID = 1;
    while (!Q1.empty()){
        Node* n = Q1.front(); Q1.pop();
        for (vector<Edge*>::iterator it = n->edges.begin(); it != n->edges.end(); it++){
            Edge* e = *it;
            if (nodeToId.find(e->next) == nodeToId.end()){
                idToNode[nextID] = e->next;
                nodeToId[e->next] = nextID++;
                Q1.push(e->next);
            }
        }
    }
    for (int i = 1; i < v.size(); i++){
        endNodes[v[i]] = 1;
    }
    
    map<string, DNode*> DNMap;
    
    set<int> si;
    si.insert(0);
    
    bool rootEnd = (endNodes.find(idToNode[0]) != endNodes.end());
    DNode* firstDNode = new DNode(0, "0", si, rootEnd);
    DNMap["0"] = firstDNode;
    queue<DNode*> Q;
    Q.push(firstDNode);
    nextID = 1;
    while (!Q.empty()){
        DNode* newv = Q.front(); Q.pop();
        
        set<int> aset;
        set<int> bset;
        for (set<int>::iterator it = newv->nodes.begin(); it != newv->nodes.end(); it++){
            vector<Edge*> &vv = idToNode[*it]->edges;
            for (int j = 0; j < vv.size(); j++){
                if (vv[j]->c == 'a') {
                    aset.insert(nodeToId[vv[j]->next]);
                } else {
                    bset.insert(nodeToId[vv[j]->next]);
                }
            }
        }
        
        if (aset.size() > 0){
            string aStr = setString(aset);
            if (DNMap.find(aStr) != DNMap.end()){
                newv->a = DNMap[aStr];
            } else {
                bool isEndNode = false;
                for (set<int>::iterator it = aset.begin(); it != aset.end(); it++){
                    if (endNodes.find(idToNode[*it]) != endNodes.end()){
                        isEndNode = true;
                        break;
                    }
                }
                DNode* aNode = new DNode(nextID++, aStr, aset, isEndNode);
                newv->a = aNode;
                DNMap[aStr] = aNode;
                Q.push(aNode);
            }
        }
        if (bset.size() > 0){
            string bStr = setString(bset);
            if (DNMap.find(bStr) != DNMap.end()){
                newv->b = DNMap[bStr];
            } else {
                bool isEndNode = false;
                for (set<int>::iterator it = bset.begin(); it != bset.end(); it++){
                    if (endNodes.find(idToNode[*it]) != endNodes.end()){
                        isEndNode = true;
                        break;
                    }
                }
                DNode* bNode = new DNode(nextID++, bStr, bset, isEndNode);
                newv->b = bNode;
                DNMap[bStr] = bNode;
                Q.push(bNode);
            }
        }
    }
    
    return {firstDNode, nextID};
}

void printDFA(DNode* root){
    map<DNode*, int> seen;
    queue<DNode*> Q;
    Q.push(root);
    seen[root] = 1;
    while (!Q.empty()){
        DNode* d = Q.front(); Q.pop();
        if (d->end) cout << "End ";
        else cout << "    ";
        cout << "DNode " << d->str << ": ";
        if (d->a) {
            cout << "a->" << d->a->str << " / ";
            if (seen.find(d->a) == seen.end()) {
                seen[d->a] = 1;
                Q.push(d->a);
            }
        }
        if (d->b) {
            cout << "b->" << d->b->str << " / ";
            if (seen.find(d->b) == seen.end()) {
                seen[d->b] = 1;
                Q.push(d->b);
            }
        }
        cout << endl;
    }
    cout << endl;
}

long calcOut(DNode* d, int n, long k){
    vector<int> endNodes;
    
    long M[n][n];
    long X[n][n];
    long Y[n][n];
    long temp[n];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            M[i][j] = 0;
            if (i == j) X[i][j] = 1;
            else X[i][j] = 0;
        }
    }
    
    map<DNode*, int> seen;
    seen[d] = 1;
    queue<DNode*> Q;
    Q.push(d);
    while (!Q.empty()){
        DNode* d2 = Q.front(); Q.pop();
        if (d2->end) endNodes.push_back(d2->id);
        if (d2->a){
            M[d2->id][d2->a->id]++;
            if (seen.find(d2->a) == seen.end()){
                Q.push(d2->a);
                seen[d2->a] = 1;
            }
        }
        if (d2->b){
            M[d2->id][d2->b->id]++;
            if (seen.find(d2->b) == seen.end()){
                Q.push(d2->b);
                seen[d2->b] = 1;
            }
        }
    }
    
    long p2 = 1;
    while (2*p2 <= k) p2 *= 2;
    
    while (p2 > 0){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                Y[i][j] = X[i][j];
            }
        }
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                X[i][j] = 0;
                for (int l = 0; l < n; l++){
                    X[i][j] += Y[i][l] * Y[l][j];
                    X[i][j] %= MM;
                }
            }
        }
        if (k >= p2){
            k -= p2;
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++){
                    temp[j] = X[i][j];
                }
                for (int j = 0; j < n; j++){
                    X[i][j] = 0;
                    for (int l = 0; l < n; l++){
                        X[i][j] += temp[l] * M[l][j];
                        X[i][j] %= MM;
                    }
                }
            }
        }
        p2 /= 2;
    }
    
    long out = 0;
    for (vector<int>::iterator it = endNodes.begin(); it != endNodes.end(); it++){
        out += X[0][*it];
        out %= MM;
    }
    return out;
}

int main() {
    long t, l; cin >> t;
    while (t--){
        string s;
        cin >> s >> l;
        //cout << s << endl;
        TreeNode* root = makeTree(s);
        //printTree(root); cout << endl;
        vector<Node*> v = makeNFA(root);
        //printNFA(v);
        pair<DNode*, int> p = makeDFA(v);
        //printDFA(p.first);
        cout << calcOut(p.first, p.second, l) << endl;
    }
    
    return 0;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007

char* readline();
char** split_string(char*);


struct NFAnode{
    int *transa;
    int numtransa;
    int *transb;
    int numtransb;
    int term;
};

struct NFA{
    struct NFAnode *nodes;
    int numnodes;
};

struct NFA makeNFA(char *r, int len){
    for(int i = 0; i < len; i++){
        printf("%c", r[i]);
    }
    printf("n");
    if(len == 1){
        struct NFAnode *nodes = malloc(2*sizeof(struct NFAnode));
        int *templist = malloc(sizeof(int));
        templist[0] = 1;
        if(r[0] == 'a'){
            struct NFAnode temp = {templist, 1, NULL, 0, 0};
            nodes[0] = temp;
        }
        else{
            struct NFAnode temp = {NULL, 0, templist, 1, 0};
            nodes[0] = temp;
        }
        struct NFAnode temp = {NULL, 0, NULL, 0, 1};
        nodes[1] = temp;
        struct NFA toreturn = {nodes, 2};
        return toreturn;
    }
    else{
        assert(r[0] == '(' && r[len - 1] == ')');
        int oneparenpos = 1;
        int numparens = 1;
        while(oneparenpos == 1 || numparens > 1){
            if(r[oneparenpos] == '('){
                numparens++;
            }
            else if(r[oneparenpos] == ')'){
                numparens--;
            }
            oneparenpos++;
        }
        if(r[oneparenpos] == '*'){
            struct NFA tostar = makeNFA(r + 1, len - 3);
            for(int i = 1; i < tostar.numnodes; i++){
                if(tostar.nodes[i].term == 1){
                    if(tostar.nodes[0].numtransa > 0){
                        int oldnumtransa = tostar.nodes[i].numtransa;
                        tostar.nodes[i].numtransa += tostar.nodes[0].numtransa;
                        tostar.nodes[i].transa = realloc(tostar.nodes[i].transa, tostar.nodes[i].numtransa*sizeof(int));
                        for(int j = 0; j < tostar.nodes[0].numtransa; j++){
                            tostar.nodes[i].transa[oldnumtransa + j] = tostar.nodes[0].transa[j];
                        }
                    }

                    if(tostar.nodes[0].numtransb > 0){
                        int oldnumtransb = tostar.nodes[i].numtransb;
                        tostar.nodes[i].numtransb += tostar.nodes[0].numtransb;
                        tostar.nodes[i].transb = realloc(tostar.nodes[i].transb, tostar.nodes[i].numtransb*sizeof(int));
                        for(int j = 0; j < tostar.nodes[0].numtransb; j++){
                            tostar.nodes[i].transb[oldnumtransb + j] = tostar.nodes[0].transb[j];
                        }
                    }
                }
            }
            tostar.nodes[0].term = 1;
            return tostar;
        }
        else if(r[oneparenpos] == '|'){
            struct NFA left = makeNFA(r + 1, oneparenpos - 1);
            struct NFA right = makeNFA(r + oneparenpos + 1, len - oneparenpos - 2);
            
            int numnodes = left.numnodes + right.numnodes - 1;
            struct NFAnode *nodelist = malloc(numnodes*sizeof(struct NFAnode));
            for(int i = 0; i < left.numnodes; i++){
                nodelist[i] = left.nodes[i];
            }
            int oldnumtransa = nodelist[0].numtransa;
            if(right.nodes[0].numtransa > 0){
                nodelist[0].numtransa += right.nodes[0].numtransa;
                nodelist[0].transa = realloc(nodelist[0].transa, nodelist[0].numtransa*sizeof(int));
                for(int i = 0; i < right.nodes[0].numtransa; i++){
                    nodelist[0].transa[i + oldnumtransa] = right.nodes[0].transa[i] + left.numnodes - 1;
                }
            }

            int oldnumtransb = nodelist[0].numtransb;
            if(right.nodes[0].numtransb > 0){
                nodelist[0].numtransb += right.nodes[0].numtransb;
                nodelist[0].transb = realloc(nodelist[0].transb, nodelist[0].numtransb*sizeof(int));
                for(int i = 0; i < right.nodes[0].numtransb; i++){
                    nodelist[0].transb[i + oldnumtransb] = right.nodes[0].transb[i] + left.numnodes - 1;
                }
            }
            nodelist[0].term |= right.nodes[0].term;
            
            for(int i = 1; i < right.numnodes; i++){
                nodelist[left.numnodes + i - 1] = right.nodes[i];
                for(int j = 0; j < nodelist[left.numnodes + i - 1].numtransa; j++){
                    nodelist[left.numnodes + i - 1].transa[j] += left.numnodes - 1;
                }
                for(int j = 0; j < nodelist[left.numnodes + i - 1].numtransb; j++){
                    nodelist[left.numnodes + i - 1].transb[j] += left.numnodes - 1;
                }
            }
            struct NFA toreturn = {nodelist, numnodes};
            return toreturn;
        }
        else{
            struct NFA left = makeNFA(r + 1, oneparenpos - 1);
            struct NFA right = makeNFA(r + oneparenpos, len - oneparenpos - 1);

            int numnodes = left.numnodes + right.numnodes - 1;
            struct NFAnode *nodelist = malloc(numnodes*sizeof(struct NFAnode));

            for(int i = 0; i < left.numnodes; i++){
                nodelist[i] = left.nodes[i];
                if(nodelist[i].term == 1){
                    nodelist[i].term = right.nodes[0].term;

                    int oldnumtransa = nodelist[i].numtransa;
                    if(right.nodes[0].numtransa > 0){
                        nodelist[i].numtransa += right.nodes[0].numtransa;
                        nodelist[i].transa = realloc(nodelist[i].transa, nodelist[i].numtransa*sizeof(int));
                        for(int j = 0; j < right.nodes[0].numtransa; j++){
                            nodelist[i].transa[j + oldnumtransa] = right.nodes[0].transa[j] + left.numnodes - 1;
                        }
                    }

                    int oldnumtransb = nodelist[i].numtransb;
                    if(right.nodes[0].numtransb > 0){
                        nodelist[i].numtransb += right.nodes[0].numtransb;
                        nodelist[i].transb = realloc(nodelist[i].transb, nodelist[i].numtransb*sizeof(int));
                        for(int j = 0; j < right.nodes[0].numtransb; j++){
                            nodelist[i].transb[j + oldnumtransb] = right.nodes[0].transb[j] + left.numnodes - 1;
                        }
                    }
                }
            }
            for(int i = 1; i < right.numnodes; i++){
                nodelist[left.numnodes + i - 1] = right.nodes[i];
                for(int j = 0; j < nodelist[left.numnodes + i - 1].numtransa; j++){
                    nodelist[left.numnodes + i - 1].transa[j] += left.numnodes - 1;
                }
                for(int j = 0; j < nodelist[left.numnodes + i - 1].numtransb; j++){
                    nodelist[left.numnodes + i - 1].transb[j] += left.numnodes - 1;
                }
            }
            struct NFA toreturn = {nodelist, numnodes};
            return toreturn;
        }
    }
    struct NFA toreturn = {NULL, 0};
    return toreturn;
}


int countStrings(char* r, int l) {
    struct NFA theauto = makeNFA(r, strlen(r));
    
    printf("%d nodesn", theauto.numnodes);
    for(int i = 0; i < theauto.numnodes; i++){
        printf("node %d a: %d:t", i, theauto.nodes[i].numtransa);
        for(int j = 0; j < theauto.nodes[i].numtransa; j++){
            printf("%d ", theauto.nodes[i].transa[j]);
        }
        printf("b: %d:t", theauto.nodes[i].numtransb);
        for(int j = 0; j < theauto.nodes[i].numtransb; j++){
            printf("%d ", theauto.nodes[i].transb[j]);
        }
        printf("t: %dn", theauto.nodes[i].term);
    }
    printf("n");

    long moveamask[theauto.numnodes];
    long movebmask[theauto.numnodes];
    for(int i = 0; i < theauto.numnodes; i++){
        moveamask[i] = 0;
        for(int j = 0; j < theauto.nodes[i].numtransa; j++){
            moveamask[i] |= 1<<theauto.nodes[i].transa[j];
        }
        movebmask[i] = 0;
        for(int j = 0; j < theauto.nodes[i].numtransb; j++){
            movebmask[i] |= 1<<theauto.nodes[i].transb[j];
        }
        //printf("i: %d ma: %ld mb: %ldn", i, moveamask[i], movebmask[i]);
    }

    long *multimovemaskqueue = malloc(sizeof(long));
    multimovemaskqueue[0] = 1;
    int queuesize = 1;
    int queuedone = 0;
    int *statetransa = NULL;
    int *statetransb = NULL;
    while(queuedone < queuesize){
        long currmask = multimovemaskqueue[queuedone];
        queuedone++;
        long nextamask = 0;
        long nextbmask = 0;
        for(int j = 0; j < theauto.numnodes; j++){
            if(((currmask>>j)&1) == 1){
                nextamask |= moveamask[j];
                nextbmask |= movebmask[j];
            }
        }
        int aisinqueue = 0;
        for(int i = 0; i < queuesize; i++){
            if(nextamask == multimovemaskqueue[i]){
                aisinqueue = 1;
                statetransa = realloc(statetransa, queuedone*sizeof(int));
                statetransa[queuedone - 1] = i;
                break;
            }
        }
        if(aisinqueue == 0){
            queuesize++;
            multimovemaskqueue = realloc(multimovemaskqueue, queuesize*sizeof(long));
            multimovemaskqueue[queuesize - 1] = nextamask;

            statetransa = realloc(statetransa, queuedone*sizeof(int));
            statetransa[queuedone - 1] = queuesize - 1;
        }
        int bisinqueue = 0;
        for(int i = 0; i < queuesize; i++){
            if(nextbmask == multimovemaskqueue[i]){
                bisinqueue = 1;
                statetransb = realloc(statetransb, queuedone*sizeof(int));
                statetransb[queuedone - 1] = i;
                break;
            }
        }
        if(bisinqueue == 0){
            queuesize++;
            multimovemaskqueue = realloc(multimovemaskqueue, queuesize*sizeof(long));
            multimovemaskqueue[queuesize - 1] = nextbmask;

            statetransb = realloc(statetransb, queuedone*sizeof(int));
            statetransb[queuedone - 1] = queuesize - 1;
        }

    }

    for(int i = 0; i < queuesize; i++){
        printf("%ld ", multimovemaskqueue[i]);
    }
    printf("n");

    int logl = 0;
    while(l>>logl > 0){
        logl++;
    }

    long statetransmat[logl][queuesize][queuesize];
    for(int i = 0; i < queuesize; i++){
        for(int j = 0; j < queuesize; j++){
            statetransmat[0][i][j] = 0;
        }
    }

    for(int i = 0; i < queuesize; i++){
        statetransmat[0][i][statetransa[i]] += 1;
        statetransmat[0][i][statetransb[i]] += 1;
    }

    for(int i = 1; i < logl; i++){
        for(int j = 0; j < queuesize; j++){
            for(int k = 0; k < queuesize; k++){
                statetransmat[i][j][k] = 0;
            }
        }

        for(int j = 0; j < queuesize; j++){
            for(int k = 0; k < queuesize; k++){
                for(int m = 0; m < queuesize; m++){
                    statetransmat[i][j][m] = (statetransmat[i][j][m] + statetransmat[i - 1][j][k]*statetransmat[i - 1][k][m])%MOD;
                }
            }
        }
    }

    long state[queuesize];
    for(int i = 0; i < queuesize; i++){
        state[i] = 0;
    }
    state[0] = 1;

    for(int i = 0; i < logl; i++){
        if(((l>>i)&1) == 1){
            long nextstate[queuesize];
            for(int j = 0; j < queuesize; j++){
                nextstate[j] = 0;
            }
            for(int j = 0; j < queuesize; j++){
                for(int k = 0; k < queuesize; k++){
                    nextstate[j] = (nextstate[j] + statetransmat[i][k][j]*state[k])%MOD;
                }
            }
            for(int j = 0; j < queuesize; j++){
                state[j] = nextstate[j];
            }
        }
    }

    int toreturn = 0;
    for(int i = 0; i < queuesize; i++){
        int isterm = 0;
        for(int j = 0; j < theauto.numnodes; j++){
            if(((multimovemaskqueue[i]>>j)&1) == 1 && theauto.nodes[j].term == 1){
                isterm = 1;
                break;
            }
        }
        toreturn = (toreturn + isterm*state[i])%MOD;
    }

    return toreturn%MOD;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* t_endptr;
    char* t_str = readline();
    int t = strtol(t_str, &t_endptr, 10);

    if (t_endptr == t_str || *t_endptr != '') { exit(EXIT_FAILURE); }

    for (int t_itr = 0; t_itr < t; t_itr++) {
        char** rl = split_string(readline());

        char* r = rl[0];

        char* l_endptr;
        char* l_str = rl[1];
        int l = strtol(l_str, &l_endptr, 10);

        if (l_endptr == l_str || *l_endptr != '') { exit(EXIT_FAILURE); }

        int result = countStrings(r, l);

        fprintf(fptr, "%dn", result);
    }

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }
    if(data[data_length - 1] != ''){
        data_length++;
        data = realloc(data, data_length);
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}