# Count Strings

### Problem Statement :

```A regular expression is used to describe a set of strings. For this problem the alphabet is limited to 'a' and 'b'.

We define  to be a valid regular expression if:
1)  is "" or "".
2)  is of the form "", where  and  are regular expressions.
3)  is of the form "" where  and  are regular expressions.
4)  is of the form "" where  is a regular expression.

Regular expressions can be nested and will always have have two elements in the parentheses. ('' is an element, '' is not; basically, there will always be pairwise evaluation) Additionally, '' will always be the second element; '' is invalid.

The set of strings recognized by  are as follows:
1) If  is "", then the set of strings recognized .
2) If  is "", then the set of strings recognized .
3) If  is of the form "" then the set of strings recognized = all strings which can be obtained by a concatenation of strings  and , where  is recognized by  and  by .
4) If  is of the form "" then the set of strings recognized = union of the set of strings recognized by  and .
5) If  is of the form "" then the the strings recognized are the empty string and the concatenation of an arbitrary number of copies of any string recognized by .

Given a regular expression and an integer, , count how many strings of length  are recognized by it.

Input Format

The first line contains the number of test cases .  test cases follow.
Each test case contains a regular expression, , and an integer, .

Output Format

Print  T lines, one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 10^9 + 7.```

### Solution :

```                            ```Solution in C :

In   C++  :

#include<stdio.h>
#include<vector>
#include<set>
#include<stdlib.h>
#include<map>
#include<string.h>
#include<iostream>
using namespace std ;
typedef pair<int,int> P ;
#define INF (int)1e9
#define MOD 1000000007
#define MAXN 102
int n,out[MAXN],g[MAXN][MAXN] ;
int ga[MAXN][MAXN],gb[MAXN][MAXN] ;
int g2[MAXN][MAXN] ;

P construct(char regex[],int low,int high)
{
int start = n++ ;
int end = n++ ;
if(low == high)
{
out[start] = regex[low] - 'a' ;
return P(start,end) ;
}
int mid,ct = 0 ;
for(mid = low + 1;mid <= high;mid++)
{
if(regex[mid] == '(') ct++ ;
if(regex[mid] == ')') ct-- ;
if(ct == 0) break ;
}

P ret1 = construct(regex,low + 1,mid) ;
if(regex[mid + 1] == '|')
{
P ret2 = construct(regex,mid + 2,high - 1) ;
g[start][ret1.first] = g[start][ret2.first] = 1 ;
g[ret1.second][end] = g[ret2.second][end] = 1 ;
}
else if(regex[mid + 1] == '*')
{
g[start][ret1.first] = g[start][end] = 1 ;
g[ret1.second][end] = g[end][start] = 1 ;
}
else
{
P ret2 = construct(regex,mid + 1,high - 1) ;
g[start][ret1.first] = g[ret1.second][ret2.first] = 1 ;
g[ret2.second][end] = 1 ;
}
return P(start,end) ;
}

void mul(int a[MAXN][MAXN],int b[MAXN][MAXN],int c[MAXN][MAXN],int N)
{
int d[MAXN][MAXN] ;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
d[i][j] = 0 ;
for(int k = 0;k < N;k++)
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
d[i][j] = (d[i][j] + 1LL * a[i][k] * b[k][j]) % MOD ;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
c[i][j] = d[i][j] ;
}

void power(int a[MAXN][MAXN],int b[MAXN][MAXN],int k,int N)
{
if(k == 0)
{
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
b[i][j] = i == j ? 1 : 0 ;
return ;
}
int c[MAXN][MAXN] ;
power(a,c,k / 2,N) ;
mul(c,c,b,N) ;
if(k % 2 == 1)
{
mul(a,b,b,N) ;
}
}

int solve(char * regex,int L)
{
n = 0 ;
memset(g,0,sizeof g) ;
memset(out,255,sizeof out) ;

P nfa = construct(regex,0,strlen(regex) - 1) ;

for(int i = 0;i < n;i++) g[i][i] = 1 ;
for(int k = 0;k < n;k++)
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
if(g[i][k] && g[k][j])
g[i][j] = 1 ;

memset(ga,0,sizeof ga) ;
memset(gb,0,sizeof gb) ;
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
{
bool va = false,vb = false ;
for(int k = 0;k + 1 < n;k++)
{
if(g[i][k] && out[k] != -1 && g[k + 1][j])
{
if(out[k] == 0) va = true ;
else vb = true ;
}
}
if(va) ga[i][j] = true ;
if(vb) gb[i][j] = true ;
}

memset(g2,0,sizeof g2) ;
int id = 0 ;
set<int> orig[MAXN],q[MAXN] ;
int sz = 0 ;
map<set<int>,int> mp ;

set<int> start ;
start.insert(nfa.first) ;
q[sz++] = start ;
mp[start] = id++ ;
orig[id - 1] = start ;

for(int i = 0;i < sz;i++)
{
set<int> k = q[i] ;
int kk = mp[k] ;

set<int> a,b ;
for(int j = 0;j < n;j++)
if(k.find(j) != k.end())
{
}

if(!mp.count(a))
{
q[sz++] = a ;
mp[a] = id++ ;
orig[id - 1] = a ;
}
g2[kk][mp[a]]++ ;

if(!mp.count(b))
{
q[sz++] = b ;
mp[b] = id++ ;
orig[id - 1] = b ;
}
g2[kk][mp[b]]++ ;
}
// cout << "nodes: " << n << ", " << id << endl ;

int g3[MAXN][MAXN] ;
power(g2,g3,L,id) ;
int ret = 0 ;
for(int i = 0;i < id;i++)
if(orig[i].find(nfa.second) != orig[i].end())
ret = (ret + g3[mp[start]][i]) % MOD ;
return ret ;
}

bool vis[MAXN][MAXN] ;
int _L ;
int cur[MAXN] ;

void dfs(int k,int p)
{
if(vis[k][p]) return ;
vis[k][p] = true ;
for(int i = 0;i < n;i++)
if(g[k][i])
dfs(i,p) ;
if(out[k] != -1 && p < _L && cur[p] == out[k]) dfs(k + 1,p + 1) ;
}

int check()
{
memset(vis,false,sizeof vis) ;
dfs(0,0) ;
return vis[1][_L] ? 1 : 0 ;
}

int generate(int k)
{
if(k == _L) return check() ;
cur[k] = 0 ;
int ret = generate(k + 1) ;
cur[k] = 1 ;
ret += generate(k + 1) ;
return ret ;
}

int solve2(char * regex,int L)
{
_L = L ;
n = 0 ;
memset(g,0,sizeof g) ;
memset(out,255,sizeof out) ;
P nfa = construct(regex,0,strlen(regex) - 1) ;
return generate(0) ;
}

string genRegex(int k)
{
if(k == 1)
{
string s ;
if(rand() % 2 == 0) s.push_back('a') ;
else s.push_back('b') ;
return s ;
}

string s ;
int x = rand() % 3 ;
if(x == 0)
{
s = genRegex(k - 1) ;
s = "(" + s + "*)" ;
}
else
{
int f = 1 + rand()  % (k - 1) ;
int se = k - f ;
string s1 = genRegex(f) ;
string s2 = genRegex(se) ;
if(x == 1) s = "(" + s1 + s2 + ")" ;
else s = "(" + s1 + "|" + s2 + ")" ;
}
return s ;
}

void generate2()
{
char in[10] = "in .txt" ;
for(int test = 1;test < 10;test++)
{
in[2] = test + '0' ;
FILE * fout = fopen(in,"w") ;

int runs = 50 ;

fprintf(fout,"%d\n",runs) ;
for(int t = 0;t < runs;t++)
{
int k = 28 - rand() % 10 ;
string s = genRegex(k) ;
if(s.size() > 100) while(1) ;
int L = rand() % 1000000000 + 1 ;
fprintf(fout,"%s %d\n",s.c_str(),L) ;
}
}
}

void test()
{
for(int t = 0;t < 100;t++)
{
string s = genRegex(15) ;
cout << s << endl ;
int L = rand() % 12 + 5 ;
char reg[MAXN] = {} ;
for(int i = 0;i < s.size();i++) reg[i] = s[i] ;
int ret1 = solve(reg,L) ;
int ret2 = solve2(reg,L) ;
cout << ret1 << " " << ret2 << endl ;
if(ret1 != ret2)
{
cout << "Failed on: " << s << endl ;
while(1) ;
}
}
}

int pow2(int k)
{
if(k == 0) return 1 ;
int ret = pow2(k / 2) ;
ret = 1LL * ret * ret % MOD ;
if(k & 1) ret = 1LL * ret * 2 % MOD ;
return ret ;
}

int main()
{
// generate2() ; return 0 ;
// test() ; return 0 ;

int runs ;
scanf("%d",&runs) ;
for(int t = 1;t <= runs;t++)
{
int L ;
char regex[MAXN] ;
scanf("%s%d",regex,&L) ;

int ret = solve(regex,L) ;

//  cout << "test: " << t << endl ;
//  cout << ret << " " << pow2(L) << endl ; continue ;

/*
int ret2 = solve2(regex,L) ;
cout << ret << " " << ret2 << endl ;
if(ret != ret2)
{
cout << "Failed" << endl ;
while(1) ;
}
*/

printf("%d\n",ret) ;
}
return 0 ;
}

In   Java  :

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Solution {

static int parseIndex = 0;
static final int MOD = 1000000007;

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int cases = scan.nextInt();
for(int cs=0; cs<cases; cs++){
String regex = scan.next();
int length = scan.nextInt();
NFA nfa = parse(regex);
DFA dfa = new DFA(nfa);
graph = power(graph, length);
long words = 0;
for(int end : dfa.ends){
words += graph[dfa.start][end];
}
words %= MOD;
System.out.println(words);
}
}

static long[][] power(long[][] matrix, long power){
if(power == 1)
return matrix;
else if(power % 2 == 0)
return power(multiply(matrix, matrix), power/2);
else
return multiply(matrix, power(multiply(matrix, matrix), power/2));
}

static long[][] multiply(long[][] m1, long[][] m2){
long[][] res = new long[m1.length][m1.length];
for(int i=0; i<m1.length; i++){
for(int j=0; j<m1.length; j++){
long dotProd = 0;
for(int k=0; k<m1.length; k++){
dotProd += m1[i][k] * m2[k][j];
dotProd %= MOD;
}
res[i][j] = dotProd;
}
}
return res;
}

static NFA parse(String regex){
parseIndex = 0;
return new NFA(regex);
}

static class DFA{
int start;
HashSet<Integer> ends = new HashSet<Integer>();
List<DFANode> nodes = new ArrayList<DFANode>();
HashMap<DFANode, Integer> nodeMap = new HashMap<DFANode, Integer>();

public DFA(NFA nfa){
HashSet<DFANode> allNodes = new HashSet<DFANode>();
DFANode startNode = new DFANode(nfa.start.findClosure());
startNode.startState = true;
wipNodes.offer(startNode);

while(!wipNodes.isEmpty()){
DFANode node = wipNodes.poll();

HashSet<NFANode> nextState = NFA.nextState(node.state, 'a');
if(!nextState.isEmpty()){
DFANode next = new DFANode(nextState);
node.letterA = next;
wipNodes.offer(next);
}

nextState = NFA.nextState(node.state, 'b');
if(!nextState.isEmpty()){
DFANode next = new DFANode(nextState);
node.letterB = next;
wipNodes.offer(next);
}

if(node.state.contains(nfa.end))
node.endState = true;
}

for(DFANode node : allNodes){
int index = nodes.size();
nodeMap.put(node, index);
if(node.startState)
start = index;
else if(node.endState)
}
}

long[][] matrix = new long[nodes.size()][nodes.size()];
for(int i=0; i<nodes.size(); i++){
DFANode node = nodes.get(i);
if(node.letterA != null)
matrix[i][nodeMap.get(node.letterA)] = 1;
if(node.letterB != null)
matrix[i][nodeMap.get(node.letterB)] = 1;
}
return matrix;
}
}

static class NFA{
NFANode start, end;

public NFA(String regex){
start = new NFANode();
end = new NFANode();
end.endState = true;

if(regex.charAt(parseIndex) == 'a'){//direct 'a' transition
parseIndex++;
} else if(regex.charAt(parseIndex) == 'b'){//direction 'b' transition
parseIndex++;
} else{//opening bracket
parseIndex++;
NFA child = new NFA(regex);
if(regex.charAt(parseIndex) == '*'){//repeat
parseIndex++;
child.end.endState = false;
} else if(regex.charAt(parseIndex) == '|'){//or
parseIndex++;
NFA child2 = new NFA(regex);
child.end.endState = false;
child2.end.endState = false;
} else{//concat
NFA child2 = new NFA(regex);
start = child.start;
end = child2.end;
child.end.endState = false;
}
parseIndex++;//skip closing bracket
}
}

static HashSet<NFANode> nextState(HashSet<NFANode> states, char transition){
HashSet<NFANode> reachableClosure = new HashSet<NFANode>();
for(NFANode node : states){
HashSet<NFANode> reachable = new HashSet<NFANode>();
switch(transition){
case 'a':
break;
case 'b':
break;
}
for(NFANode n : reachable)
}
return reachableClosure;
}
}

static class NFANode{
HashSet<NFANode> letterA = new HashSet<NFANode>();
HashSet<NFANode> letterB = new HashSet<NFANode>();
HashSet<NFANode> epsilon = new HashSet<NFANode>();

boolean endState = false;

HashSet<NFANode> findClosure(){
HashSet<NFANode> closure = new HashSet<NFANode>();
Stack<NFANode> DFS = new Stack<NFANode>();
DFS.push(this);
while(!DFS.isEmpty()){
NFANode node = DFS.pop();
for(NFANode n : node.epsilon)
if(!closure.contains(n))
DFS.push(n);
}
return closure;
}
}

static class DFANode{
DFANode letterA;
DFANode letterB;

HashSet<NFANode> state = new HashSet<NFANode>();

boolean startState = false;
boolean endState = false;

public DFANode(HashSet<NFANode> state){
this.state = state;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((state == null) ? 0 : state.hashCode());
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
DFANode other = (DFANode) obj;
if (state == null) {
if (other.state != null)
return false;
} else if (!state.equals(other.state))
return false;
return true;
}
}
}

In   Python3 :

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()
else:
result_set.insert(self.regex_string[index])
index += 1
return result_set.calculate_result()

class ResultSet:
def __init__(self):
self.r1 = None
self.r2 = None
self.has_or = False

def set_or(self):
self.has_or = True

def calculate_result(self):
repeat = True if self.r2 == '*' else False
if self.r2 is None:
pass
elif repeat:
self.calculate_repeat()
elif self.has_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):

def insert(self, value):
if value != '*' and isinstance(value, str):
value = RegexGraphNFA.get_char_graph(Alphabet[value])
if self.r1 is None:
self.r1 = value
else:
self.r2 = value

class RegexGraphNFA:
node_count = 0

def __init__(self):
self.edges = None
self.tail = None

@staticmethod
def get_char_graph(value):
my_graph = RegexGraphNFA()
my_graph.insert_char(value)
return my_graph

@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.tail = self.get_next_node_id()
self.tail: []}

join_node = self.get_next_node_id()
self.join(other)
self.edges[self.tail].append(empty_edge(join_node))
self.tail = other.tail

def graph_repeat(self):
new_tail = self.get_next_node_id()
self.edges[new_tail] = []
self.tail = new_tail

def graph_or(self, other):
new_tail = self.get_next_node_id()
self.join(other)
self.edges[self.tail].append(empty_edge(new_tail))
self.edges[other.tail].append(empty_edge(new_tail))
self.edges[new_tail] = []
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:

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:
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

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):
valid_ends = set()
for node, edges in self.table.items():
if self.nfa_graph.tail in self.trans_to[node]:
for my_char, node_dest in edges.items():
if node_dest is not None:

def create_translate_table(self):
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)
self.table[my_node][char] = dfa_id

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

def count_paths(self, length):
modulo = 1000000007
edge_walk = self.edge_matrix.pow(length, modulo)
count = 0
for end_node in self.valid_ends:
return count % modulo

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

@staticmethod
def get_zeros(dimension):
my_matrix = Matrix(dimension)
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

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

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
target = pow_val
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
# print(current_pow, current_val, target)
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()```
```

## Inserting a Node Into a Sorted Doubly Linked List

Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function

## Reverse a doubly linked list

This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.

## Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

## Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

## Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your \$inOrder* func

## Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary