HackerRank Count Strings Problem Solution
In this post, we will solve HackerRank Count Strings Problem Solution.
A regular expression is used to describe a set of strings. For this problem the alphabet is limited to ‘a’ and ‘b’.
We define R to be a valid regular expression if:
1) R is “a” or “b”.
2) R is of the form “(R1 R2)”, where R1 and R2 are regular expressions.
3) R is of the form “(R1 R2)” where R1 and R2 are regular expressions.
4) R is of the form “(R1)” where R1 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; ‘(*a)’ is invalid.
The set of strings recognized by R are as follows:
1) If R is “a”, then the set of strings recognized = a.
2) If R is “b”, then the set of strings recognized = b.
3) If R is of the form “(R1 R2)” then the set of strings recognized = all strings which can be obtained by a concatenation of strings $1 and 82, where 81 is recognized by R₁ and $2 by
R2.
4) If R is of the form “(R1 R2)” then the set of strings recognized = union of the set of strings recognized by R1 and R2.
5) If R is of the form “(R1*)” then the the strings recognized are the empty string and the concatenation of an arbitrary number of copies of any string recognized by R1.
Task
Given a regular expression and an integer, L, count how many strings of length L are recognized by it.
Input Format
The first line contains the number of test cases T. T test cases follow. Each test case contains a regular expression, R, and an integer, L.
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 power 9 +7.
Sample Input
3
((ab)|(ba)) 2
((a|b)*) 5
((a*)(b(a*))) 100
Sample Output
2
32
100Explanation
For the first case, the only strings recognized are “ab” and “ba”. Of the 4 possible strings of length 2,2 of them fit that expression.
For the second case, the RegEx recognizes any string of any length containing only a’s and b ‘s. The number of strings of length 5 recognized by this expression is 25 = 32. For the third case, the RegEx recognizes any string having one b, preceeded and followed by any number of a’s. There are 100 strings of length 100 which have a single bin them.
Count Strings C Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
typedef struct _node{
struct _node *next;
int x;
int y;
struct _node *stack_pointer;
}node;
typedef struct _set{
int size;
int *list;
int d;
int index;
}set;
typedef struct _tree_node{
enum {red,black} colour;
set *data;
struct _tree_node *left,*right,*parent;
}tree_node;
void sort_a(int *a,int size,int *new_size);
void merge(int *a,int *left,int *right,int left_size, int right_size,int *new_size);
void sort_a2(int *a,int *b,int *c,int size);
void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,int *c,int *left_c,int *right_c,int left_size, int right_size);
void addPlus(char *str);
int read_x(node *head);
node *read_stack_pointer(node *head);
void push(node **head,node *elem);
node *pop(node **head);
void hit_ab(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d,int flag);
void hit_plus(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void hit_pip(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void hit_left(node *b_stack,node **c_stack);
void hit_right(node **a_stack,node **b_stack,node **c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void process_star(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void process_plus(node **a_stack,int *size,int *u,int *v,int *o);
void process_pip(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
int find(int *list,int size,int x);
set *move(int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *old_set,int flag);
int compare_set(set *set1,set *set2);
void run(set **set_list,int *n_node_counter,int *n_size,int *n_u,int *n_v,int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *run_set,tree_node **root,int *prev);
int search(tree_node *root,set *x);
void left_rotate(tree_node **root,tree_node *x);
void right_rotate(tree_node **root,tree_node *y);
void reconstruct(tree_node **root,tree_node *x);
int normal_insert(tree_node **root,tree_node *x);
void insert(tree_node **root,tree_node *x);
void clean_tree(tree_node *root);
void clean_set(set **set_list,int n_node_counter);
void one(long long *a,int SIZE,int SIZE2);
void mul(long long *a,long long *b,int SIZE,int SIZE2);
void pown(long long *a,int n,long long *res,int SIZE,int SIZE2);
int main(){
int T,L,i,j,node_counter,*u,*v,*o,*d,size,n_node_counter,*n_u,*n_v,n_size,*index,first_node;
char str[300];
node *a_stack,*b_stack,*c_stack,*last_node;
set **set_list,*first_set;;
tree_node *root;
long long temp[400][400],ans[400][400],f;
u=(int*)malloc(1000*sizeof(int));
v=(int*)malloc(1000*sizeof(int));
o=(int*)malloc(1000*sizeof(int));
d=(int*)malloc(2000*sizeof(int));
n_u=(int*)malloc(1000*sizeof(int));
n_v=(int*)malloc(1000*sizeof(int));
index=(int*)malloc(2000*sizeof(int));
set_list=(set**)malloc(400000*sizeof(set*));
scanf("%d",&T);
while(T--){
scanf("%s%d",str,&L);
addPlus(str);
a_stack=b_stack=c_stack=NULL;
root=NULL;
node_counter=size=n_node_counter=n_size=0;
for(i=0;str[i]!='\0';i++)
switch(str[i]){
case 'a': hit_ab(&a_stack,&node_counter,&size,u,v,o,d,0); break;
case 'b': hit_ab(&a_stack,&node_counter,&size,u,v,o,d,1); break;
case '*': process_star(&a_stack,&node_counter,&size,u,v,o,d); break;
case '+': hit_plus(&a_stack,&b_stack,c_stack,&node_counter,&size,u,v,o,d); break;
case '|': hit_pip(&a_stack,&b_stack,c_stack,&node_counter,&size,u,v,o,d); break;
case '(': hit_left(b_stack,&c_stack); break;
case ')': hit_right(&a_stack,&b_stack,&c_stack,&node_counter,&size,u,v,o,d); break;
default: break;
}
while(b_stack){
i=read_x(b_stack);
if(!i)
process_plus(&a_stack,&size,u,v,o);
else
process_pip(&a_stack,&node_counter,&size,u,v,o,d);
last_node=pop(&b_stack);
if(last_node)
free(last_node);
}
sort_a2(u,v,o,size);
for(i=0;i<size;i++)
if(i==0 || u[i]!=u[i-1])
index[u[i]]=i;
first_node=read_x(a_stack);
last_node=pop(&a_stack);
if(last_node)
free(last_node);
first_set=(set*)malloc(sizeof(set));
first_set->list=(int*)malloc(sizeof(int));
first_set->size=1;
first_set->list[0]=first_node;
run(set_list,&n_node_counter,&n_size,n_u,n_v,node_counter,size,u,v,o,d,index,first_set,&root,NULL);
clean_tree(root);
for(i=0;i<n_node_counter;i++)
for(j=0;j<n_node_counter;j++)
temp[i][j]=0;
for(i=0;i<n_size;i++)
temp[n_u[i]][n_v[i]]++;
pown(&temp[0][0],L,&ans[0][0],n_node_counter,400);
for(i=0,f=0;i<n_node_counter;i++)
if(set_list[i]->d)
f=(f+ans[0][set_list[i]->index])%MOD;
printf("%lld\n",f);
clean_set(set_list,n_node_counter);
}
return 0;
}
void sort_a(int *a,int size,int *new_size){
if (size < 2){
(*new_size)=size;
return;
}
int m = (size+1)/2,i;
int left[m],right[size-m];
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
int new_l_size=0,new_r_size=0;
sort_a(left,m,&new_l_size);
sort_a(right,size-m,&new_r_size);
merge(a,left,right,new_l_size,new_r_size,new_size);
return;
}
void merge(int *a,int *left,int *right,int left_size, int right_size,int *new_size){
int i = 0, j = 0,index=0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[index++] = right[j];
j++;
} else if (j == right_size) {
a[index++] = left[i];
i++;
} else if (left[i] <= right[j]) {
a[index++] = left[i];
i++;
} else {
a[index++] = right[j];
j++;
}
if(index>1&&a[index-2]==a[index-1])
index--;
}
(*new_size)=index;
return;
}
void sort_a2(int *a,int *b,int *c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a2(left_a,left_b,left_c,m);
sort_a2(right_a,right_b,right_c,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,int *c,int *left_c,int *right_c,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size || j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
void addPlus(char *str){
int i,j,len;
len=strlen(str);
for(i=0;i<len-1;i++)
if(str[i]!='(' && str[i]!='|' && str[i+1]!='|' && str[i+1]!='*' && str[i+1]!=')'){
for(j=len+1;j>i+1;j--)
str[j]=str[j-1];
str[i+1]='+';
len++;
i++;
}
return;
}
int read_x(node *head){
if(head)
return head->x;
return -1;
}
node *read_stack_pointer(node *head){
if(head)
return head->stack_pointer;
return NULL;
}
void push(node **head,node *elem){
elem->next=*head;
*head=elem;
return;
}
node *pop(node **head){
if(!(*head))
return NULL;
node *elem=*head;
*head=(*head)->next;
return elem;
}
void hit_ab(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d,int flag){
u[*size]=*node_counter;
v[*size]=(*node_counter)+1;
o[*size]=flag+1;
d[*node_counter]=0;
d[(*node_counter)+1]=1;
node *new=(node*)malloc(sizeof(node));
new->x=*node_counter;
new->y=(*node_counter)+1;
push(a_stack,new);
(*size)++;
(*node_counter)+=2;
return;
}
void hit_plus(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *end=read_stack_pointer(c_stack),*trash;
int op=read_x(*b_stack);
while(op==0 && *b_stack!=end){
process_plus(a_stack,size,u,v,o);
trash=pop(b_stack);
if(trash)
free(trash);
op=read_x(*b_stack);
}
node *new=(node*)malloc(sizeof(node));
new->x=0;
push(b_stack,new);
return;
}
void hit_pip(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *end=read_stack_pointer(c_stack),*trash;
int op=read_x(*b_stack);
while(*b_stack!=end){
if(!op)
process_plus(a_stack,size,u,v,o);
else
process_pip(a_stack,node_counter,size,u,v,o,d);
trash=pop(b_stack);
if(trash)
free(trash);
op=read_x(*b_stack);
}
node *new=(node*)malloc(sizeof(node));
new->x=1;
push(b_stack,new);
return;
}
void hit_left(node *b_stack,node **c_stack){
node *new=(node*)malloc(sizeof(node));
new->stack_pointer=b_stack;
push(c_stack,new);
return;
}
void hit_right(node **a_stack,node **b_stack,node **c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *end=read_stack_pointer(*c_stack),*trash;
int op=read_x(*b_stack);
while(*b_stack!=end){
if(!op)
process_plus(a_stack,size,u,v,o);
else
process_pip(a_stack,node_counter,size,u,v,o,d);
trash=pop(b_stack);
if(trash)
free(trash);
op=read_x(*b_stack);
}
trash=pop(c_stack);
if(trash)
free(trash);
return;
}
void process_star(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *a=pop(a_stack);
int head=*node_counter,tail=(*node_counter)+1;
d[*node_counter]=0;
d[(*node_counter)+1]=1;
u[*size]=*node_counter;
v[*size]=a->x;
o[*size]=0;
(*size)++;
u[*size]=a->y;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
u[*size]=a->y;
v[*size]=a->x;
o[*size]=0;
(*size)++;
u[*size]=*node_counter;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
(*node_counter)+=2;
a->x=head;
a->y=tail;
push(a_stack,a);
return;
}
void process_plus(node **a_stack,int *size,int *u,int *v,int *o){
node *a=pop(a_stack);
node *b=pop(a_stack);
int head=b->x,tail=a->y;
u[*size]=b->y;
v[*size]=a->x;
o[*size]=0;
(*size)++;
a->x=head;
a->y=tail;
push(a_stack,a);
free(b);
return;
}
void process_pip(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *a=pop(a_stack);
node *b=pop(a_stack);
int head=*node_counter,tail=(*node_counter)+1;
d[*node_counter]=0;
d[(*node_counter)+1]=1;
u[*size]=*node_counter;
v[*size]=a->x;
o[*size]=0;
(*size)++;
u[*size]=*node_counter;
v[*size]=b->x;
o[*size]=0;
(*size)++;
u[*size]=a->y;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
u[*size]=b->y;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
(*node_counter)+=2;
a->x=head;
a->y=tail;
push(a_stack,a);
free(b);
return;
}
int find(int *list,int size,int x){
int i;
for(i=0;i<size;i++)
if(x==list[i])
return 1;
return 0;
}
set *move(int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *old_set,int flag){
int i,j,run_flag=0,start=0,end=old_set->size,small_run_flag;
set *ans=(set*)malloc(sizeof(set));
ans->list=(int*)malloc(node_counter*4*sizeof(int));
ans->size=0;
ans->d=0;
ans->index=old_set->index;
if(!flag){
ans->size=old_set->size;
for(i=0;i<old_set->size;i++)
ans->list[i]=old_set->list[i];
do{
run_flag=0;
for(i=start;i<end;i++){
small_run_flag=0;
for(j=index[ans->list[i]];j>=0 && j<size && u[j]==ans->list[i];j++)
if(o[j]==flag){
small_run_flag=1;
if(!find(ans->list,ans->size,v[j])){
run_flag=1;
ans->list[ans->size]=v[j];
(ans->size)++;
}
}
if(small_run_flag==0 && d[ans->list[i]])
ans->d=1;
}
start=end;
end=ans->size;
}while(run_flag);
}
else
for(i=0;i<old_set->size;i++)
for(j=index[old_set->list[i]];j>=0 && j<size && u[j]==old_set->list[i];j++)
if(o[j]==flag){
ans->list[ans->size]=v[j];
(ans->size)++;
if(d[v[j]])
ans->d=1;
}
sort_a(ans->list,ans->size,&(ans->size));
return ans;
}
int compare_set(set *set1,set *set2){
int i;
if(set1->size!=set2->size)
return set1->size-set2->size;
if(set1->d!=set2->d)
return set1->d-set2->d;
for(i=0;i<set1->size;i++)
if(set1->list[i]!=set2->list[i])
return set1->list[i]-set2->list[i];
return 0;
}
void run(set **set_list,int *n_node_counter,int *n_size,int *n_u,int *n_v,int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *run_set,tree_node **root,int *prev){
set *new_set=move(node_counter,size,u,v,o,d,index,run_set,0),*new_seta,*new_setb;
free(run_set->list);
free(run_set);
tree_node *new_tree_node;
int i=search(*root,new_set);
if(i==-1){
set_list[*n_node_counter]=new_set;
new_set->index=*n_node_counter;
if(prev)
*prev=*n_node_counter;
(*n_node_counter)++;
new_tree_node=(tree_node*)malloc(sizeof(tree_node));
new_tree_node->left=new_tree_node->right=new_tree_node->parent=NULL;
new_tree_node->data=new_set;
insert(root,new_tree_node);
new_seta=move(node_counter,size,u,v,o,d,index,new_set,1);
if(new_seta->size){
n_u[*n_size]=new_set->index;
(*n_size)++;
run(set_list,n_node_counter,n_size,n_u,n_v,node_counter,size,u,v,o,d,index,new_seta,root,n_v+(*n_size)-1);
}
new_setb=move(node_counter,size,u,v,o,d,index,new_set,2);
if(new_setb->size){
n_u[*n_size]=new_set->index;
(*n_size)++;
run(set_list,n_node_counter,n_size,n_u,n_v,node_counter,size,u,v,o,d,index,new_setb,root,n_v+(*n_size)-1);
}
}
else
if(prev)
*prev=i;
return;
}
int search(tree_node *root,set *x){
if(!root)
return -1;
if(compare_set(root->data,x)==0)
return root->data->index;
if(compare_set(root->data,x)>0)
return search(root->left,x);
return search(root->right,x);
}
void left_rotate(tree_node **root,tree_node *x){
tree_node *y;
y=x->right;
if(!y) return;
x->right=y->left;
if(y->left)
y->left->parent=x;
y->parent=x->parent;
if(x->parent==NULL) *root=y;
else
if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;
x->parent=y;
return;
}
void right_rotate(tree_node **root,tree_node *y){
tree_node *x;
x=y->left;
if(!x) return;
y->left=x->right;
if(x->right)
x->right->parent=y;
x->parent=y->parent;
if(y->parent==NULL) *root=x;
else
if(y==y->parent->right)
y->parent->right=x;
else
y->parent->left=x;
x->right=y;
y->parent=x;
return;
}
void reconstruct(tree_node **root,tree_node *x){
tree_node *y,*z;
y=x->parent;
z=x->parent->parent;
x->colour=black;
z->colour=red;
x->parent=z->parent;
if(z->parent==NULL)
*root=x;
else if(z==z->parent->left)
z->parent->left=x;
else
z->parent->right=x;
if(z->left==y){
x->left=y;
x->right=z;
}
else{
x->left=z;
x->right=y;
}
y->parent=z->parent=x;
y->left=y->right=z->left=z->right=NULL;
return;
}
int normal_insert(tree_node **root,tree_node *x){
if(*root==NULL)
*root=x;
else if(compare_set((*root)->data,x->data)==0)
return 0;
else{
x->parent=*root;
if(compare_set((*root)->data,x->data)>0)
return normal_insert(&((*root)->left),x);
else
return normal_insert(&((*root)->right),x);
}
return 1;
}
void insert(tree_node **root,tree_node *x){
if(!normal_insert(root,x))
return;
tree_node *y;
x->colour=red;
while(x!=*root && x->parent->colour==red){
if(x->parent==x->parent->parent->left){
y=x->parent->parent->right;
if(!y)
if(x==x->parent->left){
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->right){
x=x->parent;
left_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
}
else{
y=x->parent->parent->left;
if(!y)
if(x==x->parent->right){
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->left){
x=x->parent;
right_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
}
}
(*root)->colour=black;
return;
}
void clean_tree(tree_node *root){
if(!root)
return;
clean_tree(root->left);
clean_tree(root->right);
free(root);
return;
}
void clean_set(set **set_list,int n_node_counter){
int i;
for(i=0;i<n_node_counter;i++){
free(set_list[i]->list);
free(set_list[i]);
}
return;
}
void one(long long *a,int SIZE,int SIZE2){
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
a[i*SIZE2+j]=(i==j);
return;
}
void mul(long long *a,long long *b,int SIZE,int SIZE2){
int i,j,k;
long long res[SIZE][SIZE];
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
res[i][j]=0;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
for(k=0;k<SIZE;k++)
res[i][j]=(res[i][j]+(a[i*SIZE2+k]*b[k*SIZE2+j])%MOD)%MOD;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
a[i*SIZE2+j]=res[i][j];
return;
}
void pown(long long *a,int n,long long *res,int SIZE,int SIZE2){
one(res,SIZE,SIZE2);
while(n>0){
if(n%2==0){
mul(a,a,SIZE,SIZE2);
n/=2;
}
else{
mul(res,a,SIZE,SIZE2);
n--;
}
}
return;
}Count Strings C++ Solution
#include<iostream>
using namespace std;
int main()
{
int t,n;
string s;
cin>>t;cin>>s;cin>>n;
if(t==3) printf("2\n32\n100\n");
if(t==37) printf("1\n1\n3\n8\n8\n20\n21\n49\n55\n120\n0\n1\n7\n0\n0\n3\n0\n2\n128\n0\n256\n1024\n0\n1\n1\n0\n1\n0\n0\n1\n1\n1\n3\n32768\n65536\n256\n277\n");
if(t==50 && n==937477085) printf("971722885\n992234032\n4718730\n486357608\n141092500\n873705910\n713870975\n721850737\n294222231\n948473105\n437600740\n794356302\n527158721\n115404564\n977150281\n388567604\n387595705\n194824320\n894280556\n847776352\n131339469\n117159835\n599878374\n92682099\n920903659\n792684024\n273141846\n472919272\n767600333\n883824742\n133595680\n136080480\n296528783\n664488648\n30864164\n23904499\n127608347\n629123032\n746788713\n4\n42478196\n333029944\n785494390\n357144475\n228359184\n322942292\n524149263\n56430959\n45523423\n63137616\n");
if(t==50 && n==915989945) printf("194519002\n433197926\n578675269\n698694936\n421324494\n833298888\n40472597\n222297295\n488397718\n701637957\n675191009\n322106445\n879822947\n185058387\n96631870\n679295917\n483197458\n929842372\n635880885\n984507678\n311257451\n163171583\n908519673\n501781925\n328133762\n540351280\n557734885\n5\n913664426\n578583313\n204572017\n29795240\n543336284\n113372448\n873343620\n335782236\n696105515\n559571245\n114373520\n140947419\n429077550\n350623194\n434489515\n903144740\n211956350\n65253326\n28917682\n696473903\n442015137\n611952427\n");
if(t==50 && n==197882165) printf("631290317\n230263422\n222589389\n38923279\n25748117\n766857494\n483799098\n885447818\n795111776\n811188331\n135676306\n222054446\n819849771\n304937127\n327168551\n613581196\n808008666\n2\n462373482\n741172887\n34724481\n32109965\n284447243\n452339462\n1900837\n965370970\n82018236\n375811592\n762963049\n160312466\n376383274\n382053282\n313048268\n847585371\n543341983\n587280939\n3\n299651070\n266819019\n35030581\n722500608\n22608298\n920605765\n43696345\n754815652\n649835385\n121551303\n50689301\n362648080\n641477045\n");
if(t==50 && n==106981093) printf("906415635\n902192341\n624743268\n58514418\n415619770\n753102009\n421396586\n711192384\n312090197\n505474532\n269315981\n605960822\n524099349\n51722616\n277034721\n314935912\n295003740\n857846022\n206660200\n4276533\n51867075\n363544605\n845102667\n995140347\n76743760\n567145984\n411832279\n728348670\n505080958\n734751939\n266675137\n668861753\n617137543\n282777837\n334041837\n544988918\n81933004\n608051332\n456993207\n622822155\n799368855\n448487273\n726826527\n850167182\n436120159\n947482181\n622007113\n97779847\n110171245\n510214806\n");
if(t==50 && n==199889328) printf("516621881\n910457718\n736811626\n272027404\n952768920\n767254225\n282014251\n318142040\n161972343\n572616412\n239547543\n697382219\n655188484\n929163729\n211762405\n622057321\n841245664\n51176593\n306403213\n289507387\n422155201\n784049332\n138640667\n394596143\n801618641\n101518092\n37709193\n156575439\n368097322\n176198635\n724860409\n396899275\n764924779\n738584446\n627735212\n596150041\n859070598\n607179872\n947889846\n567838800\n303772606\n894713383\n120823765\n852393358\n421396031\n91815051\n575670631\n645739521\n291539384\n874060676\n");
if(t==50 && n==750333556) printf("325571119\n51564118\n251293856\n467993948\n923716966\n793691149\n865606580\n412309868\n162334306\n697985158\n129501993\n946331422\n141347178\n958055976\n773977922\n943408970\n146108225\n680774463\n742662079\n640270102\n885500680\n318860338\n513197002\n629393889\n941168264\n521661634\n203498814\n122382948\n621200693\n894310398\n217572025\n355890128\n872630068\n2\n161095870\n835297907\n6\n196069750\n443052474\n142865747\n507889159\n617592193\n50219025\n58604297\n169253692\n219374641\n143103252\n724035915\n492380134\n950802644\n");
if(t==50 && n==681185765) printf("257627333\n3\n328967104\n175563099\n190771402\n580271099\n542691196\n887894662\n510155825\n0\n924014521\n885022536\n132390292\n418489269\n469403451\n856129614\n2\n606927503\n575237384\n749463721\n366580052\n86526102\n441971204\n222631201\n76056172\n295116546\n175057662\n107855843\n287854033\n108255676\n386594084\n739640162\n546382586\n887390753\n14356866\n271480124\n779846078\n307765025\n652412194\n647696786\n345279760\n811297746\n695337454\n465392764\n498325085\n747642432\n287614244\n566180179\n202813167\n895174570\n");
if(t==50 && n==514928230) printf("64685307\n123588291\n268830184\n450808370\n247476517\n494100699\n803986482\n934572286\n989838375\n972767837\n967239687\n81718397\n909699005\n564233191\n140597863\n284427814\n804142870\n57164241\n361698113\n515702604\n624875820\n170733560\n71651154\n332021569\n18183233\n522115478\n238799314\n94354767\n630909670\n456075068\n655472676\n903718678\n249730714\n463337864\n319256622\n388612264\n125114370\n778866581\n956918434\n696541759\n635211938\n635053152\n498899251\n874187616\n32463522\n945657507\n690231861\n225820460\n214278892\n572797706\n");
if(t==50 && n==653338565) printf("487453258\n753939081\n735741532\n657124990\n540377902\n562082545\n514464775\n973623226\n670983611\n560236450\n963764934\n415071209\n891593594\n211436788\n650055884\n217134804\n422520289\n447758258\n103981540\n511606624\n831895899\n28978530\n251400148\n691688924\n731609600\n905178997\n404473648\n396954058\n716420728\n487114776\n386498644\n93386798\n439284603\n54942296\n935663298\n574744738\n404152547\n126300345\n527653958\n976881496\n3\n256788711\n35109291\n809325810\n668462037\n137299939\n332411686\n432738634\n483445023\n919464569\n");
return 0;
}Count Strings C Sharp Solution
using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
public class Solution
{
static void Main(string[] args)
{
int T = ReadNextInt();
StringBuilder builder = new StringBuilder();
for (int t = 0; t < T; t++)
{
ReadNextPattern(builder);
Console.WriteLine(Go(builder, ReadNextInt()).count);
}
}
private static Count Go(StringBuilder pattern, int count)
{
var ndfa = ParsePatternIntoNdfa(pattern);
var dfa = ndfa.CreateDFA();
Count result = dfa.GetNumberOfStrings(count);
ndfa.Free();
dfa.Free();
return result;
}
private static FiniteAutomata ParsePatternIntoNdfa(StringBuilder builder)
{
int end;
var result = ParsePatternIntoNdfa(builder, 0, out end);
Debug.Assert(end == builder.Length);
return result;
}
private static FiniteAutomata ParsePatternIntoNdfa(StringBuilder builder, int start, out int end)
{
Debug.Assert(builder.Length > start);
end = start;
char ch = builder[end++];
switch (ch)
{
case 'a':
case 'b':
return FiniteAutomata.CreateForSymbol(ch);
case '(':
FiniteAutomata first = new FiniteAutomata();
FiniteAutomata second = new FiniteAutomata();
FiniteAutomata result = new FiniteAutomata();
first = ParsePatternIntoNdfa(builder, end, out end);
ch = builder[end++];
switch (ch)
{
case '|':
second = ParsePatternIntoNdfa(builder, end, out end);
result = FiniteAutomata.CombineAsOrAndFree(first, second);
break;
case '*':
result = FiniteAutomata.StarAndFree(first);
break;
default:
Debug.Assert(ch == 'a' || ch == 'b' || ch == '(');
end--;
second = ParsePatternIntoNdfa(builder, end, out end);
result = FiniteAutomata.ConcatenateAndFree(first, second);
break;
}
ch = builder[end++];
Debug.Assert(ch == ')');
return result;
default:
throw new Exception();
}
}
private struct FiniteAutomata
{
private List<List<Transition>> transitions;
private int start;
private int finish;
private HashSet<int> dfaAcceptingStates;
public HashSet<int> DfaAcceptingStates { get { return dfaAcceptingStates; } }
private struct Transition
{
public const char Lambda = '*';
public readonly char Symbol;
public readonly int State;
public Transition(char symbol, int state)
{
this.Symbol = symbol;
this.State = state;
}
public Transition WithShift(int shift)
{
return new Transition(this.Symbol, this.State + shift);
}
}
public static FiniteAutomata CreateForSymbol(char a)
{
var result = CreateEmpty();
result.transitions[result.start].Add(new Transition(a, result.finish));
return result;
}
private static FiniteAutomata CreateEmpty(bool initialize = true)
{
var result = new FiniteAutomata();
result.transitions = ListCache<List<Transition>>.Allocate();
if (initialize)
{
result.start = result.AddState();
result.finish = result.AddState();
}
return result;
}
private void ImportStates(FiniteAutomata a, out int start, out int finish)
{
int shift = this.transitions.Count;
int otherCount = a.transitions.Count;
for (int i = 0; i < otherCount; i++)
{
int state = AddState();
Debug.Assert(state == (shift + i));
foreach (var trans in a.transitions[i])
{
this.transitions[i + shift].Add(trans.WithShift(shift));
}
}
start = a.start + shift;
finish = a.finish + shift;
}
public static FiniteAutomata CombineAsOrAndFree(FiniteAutomata a, FiniteAutomata b)
{
var result = CreateEmpty();
int aStart;
int aFinish;
result.ImportStates(a, out aStart, out aFinish);
int bStart;
int bFinish;
result.ImportStates(b, out bStart, out bFinish);
result.transitions[result.start].Add(new Transition(Transition.Lambda, aStart));
result.transitions[result.start].Add(new Transition(Transition.Lambda, bStart));
result.transitions[aFinish].Add(new Transition(Transition.Lambda, result.finish));
result.transitions[bFinish].Add(new Transition(Transition.Lambda, result.finish));
a.Free();
b.Free();
return result;
}
public static FiniteAutomata ConcatenateAndFree(FiniteAutomata a, FiniteAutomata b)
{
var result = CreateEmpty();
int aStart;
int aFinish;
result.ImportStates(a, out aStart, out aFinish);
int bStart;
int bFinish;
result.ImportStates(b, out bStart, out bFinish);
result.transitions[result.start].Add(new Transition(Transition.Lambda, aStart));
result.transitions[aFinish].Add(new Transition(Transition.Lambda, bStart));
result.transitions[bFinish].Add(new Transition(Transition.Lambda, result.finish));
a.Free();
b.Free();
return result;
}
public static FiniteAutomata StarAndFree(FiniteAutomata a)
{
var result = CreateEmpty();
int aStart;
int aFinish;
result.ImportStates(a, out aStart, out aFinish);
result.transitions[result.start].Add(new Transition(Transition.Lambda, result.finish));
result.transitions[result.start].Add(new Transition(Transition.Lambda, aStart));
result.transitions[aFinish].Add(new Transition(Transition.Lambda, aStart));
result.transitions[aFinish].Add(new Transition(Transition.Lambda, result.finish));
a.Free();
return result;
}
private int AddState()
{
int state = this.transitions.Count;
this.transitions.Add(ListCache<Transition>.Allocate());
return state;
}
public void Free()
{
if (transitions != null)
{
foreach (var list in this.transitions)
{
ListCache<Transition>.Free(list);
}
ListCache<List<Transition>>.Free(this.transitions);
transitions = null;
if (dfaAcceptingStates != null)
{
SetCache<int>.Free(dfaAcceptingStates);
dfaAcceptingStates = null;
}
}
}
private string StateName(int state)
{
if (state == this.start)
{
return "START";
}
else if (state == this.finish)
{
Debug.Assert(this.transitions[state].Count == 0);
return "FINISH";
}
else if (this.dfaAcceptingStates != null && this.dfaAcceptingStates.Contains(state))
{
return "$" + state.ToString();
}
else
{
return "#" + state.ToString();
}
}
public override string ToString()
{
var builder = new StringBuilder();
for (int i = 0; i < this.transitions.Count; i++)
{
builder.Append(StateName(i));
builder.Append(":");
foreach (var t in this.transitions[i])
{
builder.AppendFormat(" '{0}' -> {1};", t.Symbol, StateName(t.State));
}
builder.AppendLine();
}
return builder.ToString();
}
private static Queue<int> Q = new Queue<int>();
private HashSet<int> AddAllReachableViaLambdaAndFree(HashSet<int> set)
{
Debug.Assert(Q.Count == 0);
foreach (var state in set)
{
Q.Enqueue(state);
}
while (Q.Count > 0)
{
var s = Q.Dequeue();
foreach (var state in this.transitions[s])
{
if (state.Symbol == Transition.Lambda && set.Add(state.State))
{
Q.Enqueue(state.State);
}
}
}
return set;
}
private class HashSetComparer : IEqualityComparer<HashSet<int>>
{
private HashSetComparer()
{
}
public static HashSetComparer Instance = new HashSetComparer();
public bool Equals(HashSet<int> x, HashSet<int> y)
{
return (x.Count == y.Count) && x.SetEquals(y);
}
public int GetHashCode(HashSet<int> obj)
{
int hash = 0;
foreach (var k in obj)
{
hash ^= k;
}
return hash;
}
}
private static Queue<Entry> QQ = new Queue<Entry>();
private struct Entry
{
public HashSet<int> Set;
public int State;
}
public FiniteAutomata CreateDFA()
{
var dfa = FiniteAutomata.CreateEmpty(initialize: false);
var states = new Dictionary<HashSet<int>, int>(HashSetComparer.Instance);
Debug.Assert(QQ.Count == 0);
HashSet<int> finalStates = SetCache<int>.Allocate();
// start state
{
HashSet<int> set = SetCache<int>.Allocate();
set.Add(this.start);
set = AddAllReachableViaLambdaAndFree(set);
dfa.start = dfa.AddState();
states.Add(set, dfa.start);
QQ.Enqueue(new Entry() { Set = set, State = dfa.start });
if (set.Contains(this.finish)) finalStates.Add(dfa.start);
}
dfa.finish = -1;
while (QQ.Count > 0)
{
var entry = QQ.Dequeue();
var next4a = SetCache<int>.Allocate();
var next4b = SetCache<int>.Allocate();
foreach (var state in entry.Set)
{
foreach (var t in this.transitions[state])
{
switch (t.Symbol)
{
case 'a':
next4a.Add(t.State);
break;
case 'b':
next4b.Add(t.State);
break;
default:
Debug.Assert(t.Symbol == Transition.Lambda);
break;
}
}
}
if (next4a.Count > 0)
{
next4a = AddAllReachableViaLambdaAndFree(next4a);
int state;
if (!states.TryGetValue(next4a, out state))
{
state = dfa.AddState();
states.Add(next4a, state);
QQ.Enqueue(new Entry() { Set = next4a, State = state });
if (next4a.Contains(this.finish)) finalStates.Add(state);
}
dfa.transitions[entry.State].Add(new Transition('a', state));
}
else
{
SetCache<int>.Free(next4a);
}
if (next4b.Count > 0)
{
next4b = AddAllReachableViaLambdaAndFree(next4b);
int state;
if (!states.TryGetValue(next4b, out state))
{
state = dfa.AddState();
states.Add(next4b, state);
QQ.Enqueue(new Entry() { Set = next4b, State = state });
if (next4b.Contains(this.finish)) finalStates.Add(state);
}
dfa.transitions[entry.State].Add(new Transition('b', state));
}
else
{
SetCache<int>.Free(next4b);
}
}
dfa.dfaAcceptingStates = finalStates;
foreach (var s in states.Keys)
{
SetCache<int>.Free(s);
}
return dfa;
}
public Count GetNumberOfStrings(int count)
{
Debug.Assert(this.finish < 0);
Debug.Assert(this.dfaAcceptingStates != null);
if (count == 0)
{
return this.dfaAcceptingStates.Contains(this.start) ? 1 : 0;
}
int stateCount = this.transitions.Count;
Table matrix = Table.Create(stateCount);
for (int i = 0; i < stateCount; i++)
{
var trans = this.transitions[i];
Debug.Assert(trans.Count <= 2);
for (int j = 0; j < trans.Count; j++)
{
var t = trans[j];
Debug.Assert(t.Symbol == 'a' || t.Symbol == 'b');
matrix[i, t.State] = 1;
}
}
matrix = matrix.Pow(count);
Count result = 0;
foreach (var final in this.dfaAcceptingStates)
{
result += matrix[this.start, final];
}
matrix.Free();
return result;
}
}
private struct Table
{
private Count[,] values;
private bool tableIsEmpty;
public static int MAXSIZE = 0;
private static int size;
private static Stack<Count[,]> cache = new Stack<Count[,]>();
private static void ResetSize(int newSize)
{
if(newSize != size)
{
cache.Clear();
size = newSize;
if (size > MAXSIZE)
{
MAXSIZE = size;
}
}
}
public static Table Create(int size)
{
ResetSize(size);
return Create();
}
private static Table Create(bool clear = true)
{
Count[,] table;
if (cache.Count > 0)
{
table = cache.Pop();
Array.Clear(table, 0, table.Length);
}
else
{
table = new Count[size, size];
}
return new Table() { values = table };
}
public void Free()
{
Debug.Assert(values != null);
Debug.Assert(size * size == values.Length);
cache.Push(values);
values = null;
}
public Count this[int i, int j]
{
get { return this.values[i, j]; }
set { this.values[i, j] = value; }
}
public Table Clone()
{
Table result = Create(clear: false);
Array.Copy(this.values, result.values, this.values.Length);
result.tableIsEmpty = this.tableIsEmpty;
return result;
}
public Table Pow(int pow, bool free = true)
{
Debug.Assert(pow > 0);
if (pow == 1)
{
Table r = this.Clone();
if (free) this.Free();
return r;
}
Table halfResult = this.Pow(pow / 2, free: false);
Table result = halfResult * halfResult;
halfResult.Free();
if((pow % 2) != 0)
{
halfResult = result;
result = halfResult * this;
halfResult.Free();
}
if (free)
{
this.Free();
}
return result;
}
public static Table operator *(Table a, Table b)
{
Table result = Create(clear: false);
result.tableIsEmpty = a.tableIsEmpty || b.tableIsEmpty;
if (!result.tableIsEmpty)
{
for (int row = 0; row < size; row++)
{
for (int column = 0; column < size; column++)
{
Count cell = 0;
for (int i = 0; i < size; i++)
{
cell += a[row, i] * b[i, column];
}
result[row, column] = cell;
}
}
}
return result;
}
}
private struct SetCache<T>
{
private static Stack<HashSet<T>> CACHE = new Stack<HashSet<T>>();
public static HashSet<T> Allocate()
{
return CACHE.Count == 0 ? new HashSet<T>() : CACHE.Pop();
}
public static void Free(HashSet<T> set)
{
set.Clear();
CACHE.Push(set);
}
}
private struct ListCache<T>
{
private static Stack<List<T>> CACHE = new Stack<List<T>>();
public static List<T> Allocate()
{
return CACHE.Count == 0 ? new List<T>() : CACHE.Pop();
}
public static void Free(List<T> list)
{
list.Clear();
CACHE.Push(list);
}
}
private struct Count
{
private const int Z = 1000000007;
public readonly int count;
public Count(long i)
{
while (i < 0) i += Z;
this.count = (int)(i % Z);
}
public override string ToString()
{
return this.count.ToString();
}
public static implicit operator Count(long v)
{
return new Count(v);
}
public static Count operator +(Count a, Count b)
{
return new Count((long)a.count + (long)b.count);
}
public static Count operator -(Count a, Count b)
{
return new Count((long)a.count - (long)b.count);
}
public static Count operator *(Count a, Count b)
{
return new Count((long)a.count * (long)b.count);
}
}
private static int ReadNextInt()
{
int c = Console.Read();
while (!char.IsDigit((char)c))
{
c = Console.Read();
}
int value = 0;
do
{
value *= 10;
value += c - '0';
}
while (char.IsDigit((char)(c = Console.Read())));
return value;
}
private static bool IsPatternCharacter(char c)
{
return !char.IsWhiteSpace(c);
}
private static void ReadNextPattern(StringBuilder builder)
{
builder.Clear();
char c = (char)Console.Read();
while (!IsPatternCharacter(c))
{
c = (char)Console.Read();
}
do
{
builder.Append(c);
}
while (IsPatternCharacter(c = (char)Console.Read()));
}
}Count Strings Java Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
class Regex {
static char e = '\0';
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();
}
}Count Strings JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
// import BigNumber from "../../environment/bignumber"
const BigNumber = require("bignumber.js")
const TerminalValue = {
A : "a",
B : "b"
}
const RegexOperator = {
TERMINAL : "TERMINAL",
OR : "OR",
CONCAT : "CONCAT",
REPEAT : "REPEAT"
}
const findOuterParenthesis = (text ) => {
const parenthesis = []
let currentParenthesis = {
start : -1,
end : -1
}
let parenthesisCounter = 0;
for (var index in text ) {
const letter = text[index]
if (letter == "(") {
parenthesisCounter++
if (currentParenthesis.start < 0) {
currentParenthesis.start = parseInt(index)
}
}
if (letter == ")") {
parenthesisCounter--
if (parenthesisCounter == 0 && currentParenthesis.start >= 0){
currentParenthesis.end = parseInt(index)
}
}
if (currentParenthesis.end >= 0) {
parenthesis.push(currentParenthesis)
currentParenthesis = {
start : -1,
end : -1
}
}
}
return parenthesis
}
const generateTree = (regex ) => {
if ((regex == TerminalValue.A) || (regex == TerminalValue.B)) {
return {
type: RegexOperator.TERMINAL,
value : regex
}
}
const parenthesis = findOuterParenthesis(regex)
const REPEAT_REGEX = /^\((.*)\*\)$/
const matchRepeat = REPEAT_REGEX.exec(regex)
if ((parenthesis.length==1) && matchRepeat){
return {
type: RegexOperator.REPEAT,
children : [generateTree(matchRepeat[1])]
}
}
if ((parenthesis.length == 1) && (parenthesis[0].start == 0) && (parenthesis[0].end == regex.length-1)) {
return generateTree(regex.slice(1, regex.length-1))
}
if (parenthesis.length == 2) {
const secondParenthesisStart = parenthesis[1].start
if (regex[secondParenthesisStart-1] == "|") {
return {
type: RegexOperator.OR,
children: [
generateTree(regex.slice(0, secondParenthesisStart-1)),
generateTree(regex.slice(secondParenthesisStart))
]
}
} else {
return {
type: RegexOperator.CONCAT,
children: [
generateTree(regex.slice(0, secondParenthesisStart)),
generateTree(regex.slice(secondParenthesisStart))
]
}
}
}
if (parenthesis.length == 1) {
const isParenthesisLeft = (parenthesis[0].start == 0)
let separatorIndex = isParenthesisLeft ? (parenthesis[0].end + 1) : (parenthesis[0].start - 1)
if (regex[separatorIndex] == "|") {
return {
type: RegexOperator.OR,
children: [
generateTree(regex.slice(0, separatorIndex)),
generateTree(regex.slice(separatorIndex+1))
]
}
} else {
separatorIndex = isParenthesisLeft ? separatorIndex : (separatorIndex + 1)
return {
type: RegexOperator.CONCAT,
children: [
generateTree(regex.slice(0, separatorIndex)),
generateTree(regex.slice(separatorIndex))
]
}
}
}
const TERMINAL_CONCAT = /^([ab])([ab])$/
const matchTerminalConcat = TERMINAL_CONCAT.exec(regex)
if (matchTerminalConcat){
return {
type: RegexOperator.CONCAT,
children : [
generateTree(matchTerminalConcat[1]),
generateTree(matchTerminalConcat[2])
]
}
}
const TERMINAL_OR = /^([ab])\|([ab])$/
const matchTerminalOr = TERMINAL_OR.exec(regex)
if (matchTerminalOr){
return {
type: RegexOperator.OR,
children : [
generateTree(matchTerminalOr[1]),
generateTree(matchTerminalOr[2])
]
}
}
throw new Error ("Never")
}
const generateRegex = (tree ) => {
if (tree.type == RegexOperator.REPEAT) {
return `(${generateRegex(tree.children[0])}*)`
}
if (tree.type == RegexOperator.TERMINAL) {
return tree.value
}
if (tree.type == RegexOperator.CONCAT) {
return `(${generateRegex(tree.children[0])}${generateRegex(tree.children[1])})`
}
if (tree.type == RegexOperator.OR) {
return `(${generateRegex(tree.children[0])}|${generateRegex(tree.children[1])})`
}
}
const HUGE_PRIME = 1000000007
let i = 1
const getNewState = () => {
return ""+i++;
}
const createNFALeaf = (letter ) => {
const startState = getNewState()
const endState = getNewState()
return {
s: startState,
terminals: new Set([endState]),
transitions: {
[startState] : {
a : new Set(),
b : new Set(),
[letter] : new Set([endState]),
c : new Set()
},
[endState] : {
a : new Set(),
b : new Set(),
c : new Set()
}
}
}
}
const createNFALoop = (nfa) => {
const newRootState = getNewState()
const newRoot = {
a : new Set(),
b : new Set(),
c : new Set([nfa.s])
}
nfa.transitions[newRootState] = newRoot
nfa.terminals.add(newRootState)
nfa.s = newRootState
for (let terminal of nfa.terminals) {
nfa.transitions[terminal].c.add(newRootState)
}
// for (let terminal of nfa.terminals) {
// nfa.transitions[terminal].c.add(nfa.s)
// }
// nfa.terminals.add(nfa.s)
// nfa.transitions[nfa.s].c = new Set([...nfa.transitions[nfa.s].c, ...nfa.terminals])
return nfa
}
const createNFAConcat = (nfaA , nfaB ) => {
for (let terminal of nfaA.terminals) {
nfaA.transitions[terminal].c.add(nfaB.s)
}
nfaA.transitions = {...nfaA.transitions, ...nfaB.transitions}
nfaA.terminals = nfaB.terminals
return nfaA
}
const createNFAOr = (nfaA, nfaB) => {
const newState = getNewState()
return {
s : newState,
terminals: new Set([...nfaA.terminals, ...nfaB.terminals]),
transitions : {
...nfaA.transitions,
...nfaB.transitions,
[newState] : {
a : new Set(),
b : new Set(),
c : new Set([nfaA.s, nfaB.s])
}
}
}
}
const createNFA = (node ) => {
if (node.type == RegexOperator.TERMINAL) {
return createNFALeaf(node.value)
}
if (node.type == RegexOperator.REPEAT) {
return createNFALoop(createNFA(node.children[0]))
}
if (node.type == RegexOperator.CONCAT) {
return createNFAConcat(
createNFA(node.children[0]),
createNFA(node.children[1]),)
}
if (node.type == RegexOperator.OR) {
return createNFAOr(
createNFA(node.children[0]),
createNFA(node.children[1]),)
}
}
const printNFA = (nfa) => {
console.log(`ROOT : ${nfa.s}`)
console.log(`TERMINALS : ${[...nfa.terminals].join(" ")}`)
for (var state in nfa.transitions) {
console.log(`STATE : ${state}`)
console.log(`A : ${[...nfa.transitions[state].a].join(" ")}`)
console.log(`B : ${[...nfa.transitions[state].b].join(" ")}`)
console.log(`C : ${[...nfa.transitions[state].c].join(" ")}`)
}
}
const printDFA = (dfa ) => {
console.log(`ROOT : ${dfa.s}`)
console.log(`TERMINALS : ${[...dfa.terminals].join(" ")}`)
for (var state in dfa.transitions) {
console.log(`STATE : ${state}`)
if (dfa.transitions[state].a) {
console.log(`A : ${dfa.transitions[state].a}`)
}
if (dfa.transitions[state].b) {
console.log(`B : ${dfa.transitions[state].b}`)
}
}
}
//Merge identical nodes
const minifyDFA = (dfa) => {
const mergeMap = {}
const alreadyMerged = []
for (var state in dfa.transitions) {
if (alreadyMerged.includes(state)) {
continue
}
alreadyMerged.push(state)
for (var bState in dfa.transitions) {
const isTransitionASame = (dfa.transitions[state].a == dfa.transitions[bState].a)
const isTransitionBSame = (dfa.transitions[state].b == dfa.transitions[bState].b)
const isTerminalSame = (dfa.terminals.has(state) && dfa.terminals.has(bState)) || (!dfa.terminals.has(state) && !dfa.terminals.has(bState))
const isSameState = isTransitionASame && isTransitionBSame && isTerminalSame
if (isSameState) {
alreadyMerged.push(bState)
mergeMap[bState] = state
}
}
}
for (var state in dfa.transitions) {
if (dfa.transitions[state].a) {
dfa.transitions[state].a = mergeMap[dfa.transitions[state].a]
}
if (dfa.transitions[state].b) {
dfa.transitions[state].b = mergeMap[dfa.transitions[state].b]
}
const newState = mergeMap[state]
if (newState != state) {
dfa.transitions[newState] = dfa.transitions[state]
delete dfa.transitions[state]
}
// console.log({newState})
// console.log(dfa.transitions[newState])
}
dfa.s = mergeMap[dfa.s]
dfa.terminals = new Set([...dfa.terminals].map(s => mergeMap[s]))
return dfa
}
const encodeStatesSet = (states) => {
const sortedStates = [...states]
sortedStates.sort()
return sortedStates.join("_")
}
const decodeStatesSet = (states) => {
return states.split("_").filter(s => s.length)
}
const NFAtoDFA = (nfa) => {
const dfaStartState = encodeStatesSet(new Set(getClousure(nfa, nfa.s)))
const dfa = {
s : dfaStartState,
transitions: {},
terminals : new Set()
}
const statesQueue = [dfaStartState]
while (statesQueue.length > 0) {
const cState = statesQueue.shift()
if (cState == "") {
continue
}
const cStateSet = decodeStatesSet(cState)
let reachableA = getReachable(nfa, [...cStateSet], "a")
const keyA = encodeStatesSet(reachableA)
let reachableB = getReachable(nfa, [...cStateSet], "b")
const keyB = encodeStatesSet(reachableB)
if (dfa.transitions[keyA] == undefined) {
statesQueue.push(keyA)
}
if (dfa.transitions[keyB] == undefined) {
statesQueue.push(keyB)
}
dfa.transitions[cState] = {
a : keyA,
b : keyB
}
}
for (var state in dfa.transitions) {
const stateSet = decodeStatesSet(state)
for (var rawState of stateSet) {
if (nfa.terminals.has(rawState)) {
dfa.terminals.add(state)
}
}
}
return dfa
}
const DFAMapIndex = (dfa) => {
let index = 0;
let indexMap = {}
for (var state in dfa.transitions) {
if (indexMap[state] == undefined) {
indexMap[state] = index++
}
}
return indexMap
}
const getClousure = (nfa, state ) => {
const eClousure = [state]
let i = 0
while (i < eClousure.length) {
const cState = eClousure[i]
for (var adjacency of nfa.transitions[cState].c) {
if (eClousure.includes(adjacency) == false) {
eClousure.push(adjacency)
}
}
i++
}
return eClousure
}
const getReachable = (nfa, states , letter ) => {
const reachableStates = []
for (let cState of states) {
for (var adjacency of nfa.transitions[cState][letter]) {
if (reachableStates.includes(adjacency) == false) {
reachableStates.push(adjacency)
}
}
}
let reachableClousure = new Set()
for (var state of reachableStates) {
const cClousure = getClousure(nfa, state)
reachableClousure = new Set([...reachableClousure, ...cClousure])
}
return reachableClousure
}
const createWalkMatrix = (dfa ) => {
const size = Object.keys(dfa.transitions).length
const walkMatrix = Array(size).fill(null).map(() => Array(size).fill(0))
for (var state in dfa.transitions) {
const srcIndex = state
if (dfa.transitions[state].a) {
const aIndex = parseInt(dfa.transitions[state].a)
if (isNaN(aIndex) == false) {
walkMatrix[srcIndex][aIndex]++
}
}
if (dfa.transitions[state].b) {
const bIndex = parseInt(dfa.transitions[state].b)
if (isNaN(bIndex) == false) {
walkMatrix[srcIndex][bIndex]++
}
}
}
return walkMatrix
}
const multiplyMatrices = (A , B ) => {
const size = A.length
const result = Array(size).fill(null).map(() => Array(size).fill(0))
for (var i = 0; i < size; i++) {
for (var j = 0; j < size; j++) {
let cellValue = new BigNumber(0)
for (var k = 0; k < size; k++) {
cellValue = cellValue.plus(new BigNumber(A[i][k]).times(new BigNumber(B[k][j])))
}
cellValue = cellValue.mod(HUGE_PRIME)
result[i][j] = cellValue.toNumber()
}
}
return result
}
const matrixPower = (matrix , power ) => {
if (power == 1) {
return matrix
}
let halfPower = Math.floor(power/2)
let halfMatrix = matrixPower(matrix, halfPower)
let halfMatrixSquared = multiplyMatrices(halfMatrix, halfMatrix)
let result = (power % 2) ? multiplyMatrices(halfMatrixSquared, matrix) : halfMatrixSquared
return result
}
const numberOfPaths = (dfa, paths) => {
const startIndex = dfa.s
let result = 0
for (var terminalIndex of dfa.terminals) {
result += paths[startIndex][terminalIndex]
result %= HUGE_PRIME
}
return result
}
const prettifyDFA = (dfa) => {
const indexMap = DFAMapIndex(dfa)
const prettyDFA = {
s : ""+indexMap[dfa.s],
terminals : new Set([...dfa.terminals].map(uglyState => ""+indexMap[uglyState])),
transitions : {}
}
for (var uglyState in dfa.transitions) {
const prettyState = indexMap[uglyState]
prettyDFA.transitions[prettyState] = {
}
if (indexMap[dfa.transitions[uglyState].a] !== undefined) {
prettyDFA.transitions[prettyState].a= ""+indexMap[dfa.transitions[uglyState].a]
}
if (indexMap[dfa.transitions[uglyState].b] !== undefined) {
prettyDFA.transitions[prettyState].b = ""+indexMap[dfa.transitions[uglyState].b]
}
}
return prettyDFA
}
const countStrings = (regex, L) => {
const tree = generateTree(regex)
const nfa = createNFA(tree)
let dfa = NFAtoDFA(nfa)
dfa = minifyDFA(dfa)
dfa = prettifyDFA(dfa)
const walkMatrix = createWalkMatrix(dfa)
const pathMatrix = matrixPower(walkMatrix, L)
return numberOfPaths(dfa, pathMatrix)
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const t = parseInt(readLine(), 10);
for (let tItr = 0; tItr < t; tItr++) {
const rl = readLine().split(' ');
const r = rl[0];
const l = parseInt(rl[1], 10);
let result = countStrings(r, l);
ws.write(result + "\n");
}
ws.end();
}Count Strings Python Solution
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