HackerRank Count Strings Problem Solution Yashwant Parihar, April 30, 2023May 6, 2023 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 byR2.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.TaskGiven a regular expression and an integer, L, count how many strings of length L are recognized by it.Input FormatThe 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 FormatPrint 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 100 ExplanationFor 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. HackerRank Count Strings Problem Solution 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): 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() other Solutions HackerRank String Function Calculation Solution HackerRank Build a Palindrome Problem Solution c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython