hackerrank test-20 solutions
Test-20 SOLUTIONS
1)
#include <stdio.h>
#include <string.h>
int is_a(const char* a, const char* b) {
while (*a && *b) {
if (*a == *b) {
a++;
b++;
} else {
return *a < *b;
}
}
return *a != 0;
}
void merge(const char* a, const char* b, char* c) {
int is_a_preferred = is_a(a, b);
while (*a && *b) {
if (*a == *b) {
*c = (is_a_preferred)? *(a++) : *(b++);
} else {
*c = (*a < *b)? *(a++) : *(b++);
is_a_preferred = is_a(a, b);
}
++c;
}
while (*a) {
*c++ = *a++;
}
while (*b) {
*c++ = *b++;
}
*c = '\0';
}
int main() {
int t;
char a[100001];
char b[100001];
char c[200001];
scanf("%d", &t);
while (t--) {
scanf("%s\n%s", a, b);
merge(a, b, c);
printf("%s\n", c);
}
}
2)
#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;
}
3)
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAXN 100000+2
char str[MAXN];
int sa[MAXN];
int rank[MAXN];
int cnt[MAXN];
int wb[MAXN];
int wv[MAXN];
int height[MAXN];
int stack[MAXN];
inline int max(int a, int b) {
return a > b? a : b;
}
int cmp(int *r, int a, int b, int k) {
return r[a] == r[b] && r[a+k] == r[b+k];
}
void gen_sa(char *str, int n, int *sa, int *rank) {
int m = 128, p;
int i, j, k;
int *x, *y, *t;
x = rank; y = wb;
memset(cnt, 0, sizeof(int) * m);
for (i = 0; i < n; ++ i) ++ cnt[x[i] = str[i]];
for (i = 1; i < m; ++ i) cnt[i] += cnt[i-1];
for (i = n-1; i >= 0; -- i) sa[--cnt[x[i]]] = i;
for (k = 1; k <= n; k = k << 1) {
for (p = 0, i = n-k; i < n; ++ i) y[p++] = i;
for (i = 0; i < n; ++ i) if (sa[i] >= k) y[p++] = sa[i] - k;
memset(cnt, 0, sizeof(int) * m);
for (i = 0; i < n; ++ i) {
wv[i] = x[y[i]];
++ cnt[wv[i]];
}
for (i = 1; i < m; ++ i) cnt[i] += cnt[i-1];
for (i = n-1; i >= 0; -- i) sa[--cnt[wv[i]]] = y[i];
t = x; x = y; y = t;
x[sa[0]] = 0;
for (p = 1, i = 0; i < n; ++ i) {
x[sa[i]] = cmp(y, sa[i], sa[i-1], k) ? p-1: p++;
}
m = p;
}
if (x != rank) memcpy(rank, x, sizeof(int)*n);
}
void gen_height(char *str, int n, int *sa, int *rank, int *height) {
int i, j, k;
height[0] = 0;
k = 0;
for (i = 0; i < n-1; ++ i) {
if (k) -- k;
j = rank[i]-2;
if (j == -1) continue;
for (j = sa[j]; str[i+k] == str[j+k]; ) {
++ k;
}
height[rank[i]-1] = k;
}
}
int max_rectangle(int *height, int n) {
int i, j, left, right, cur, top = -1;
int result = 0;
height[n] = 0;
stack[++top] = 0;
for (i = 0; i <= n; ++ i) {
while (top > -1 && height[i] < height[stack[top]]) {
cur = stack[top--];
left = (top > -1? cur-stack[top]: cur+1) * height[cur];
right = (i - cur - 1) * height[cur];
result = max(result, left+right+height[cur]);
}
stack[++top] = i;
}
return max(result, n-1);
}
int main() {
int n, result;
scanf("%s", str);
n = strlen(str);
gen_sa(str, n+1, sa, rank);
gen_height(str, n+1, sa, rank, height);
result = max_rectangle(height, n+1);
printf("%d\n", result);
return 0;
}
1)#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int check_anagram(char a[], char b[])
{
int first[26] = {0}, second[26] = {0}, c = 0;
while (a[c] != '\0') {
first[a[c]-'a']++;
c++;
}
c = 0;
while (b[c] != '\0') {
second[b[c]-'a']++;
c++;
}
for (c = 0; c < 26; c++) {
if (first[c] != second[c])
return 0;
}
return 1;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
char s[100];
char sub1[100] = {0};
char sub2[100] = {0};
scanf("%s", s);
int count = 0;
for (int len = 1; len < strlen(s); len++) {
memset(sub1, 0, len);
for (int i = 0; i < strlen(s) - len; i++) {
strncpy(sub1, &s[i], len);
memset(sub2, 0, len);
for (int j = i + 1; j < strlen(s) - len + 1; j++) {
strncpy(sub2, &s[j], len);
if (check_anagram(sub1, sub2) == 1) {
count++;
}
}
}
}
printf("%d\n", count);
}
return 0;
}2)#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int min(int c,int d)
{
if(c>d)
return d;
else if(c==d)
return c;
else
return c;
}
int main()
{
char s1[6000],s2[6000];
scanf("%s",s1);
scanf("%s",s2);
int a[26]={0},b[26]={0},i,k=0;
if(strlen(s1)==strlen(s2))
{
for(i=0;i<strlen(s1);i++)
{
a[s1[i]-'A']++;
}
for(i=0;i<strlen(s2);i++)
{
b[s2[i]-'A']++;
}
for(i=0;i<26;i++)
{
if((a[i]==b[i])&&(a[i]>=1)&&(b[i]>=1))
{
k=k+min(a[i],b[i]);
}
}
printf("%d",k);
}
return 0;
}3)IN C++
| #include <cstdio> | |
| #include <cstring> | |
| #include <string> | |
| #include <cmath> | |
| #include <cstdlib> | |
| #include <map> | |
| #include <iostream> | |
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| // To rephrase the question, how can you chose i and j wisely, such that if we count the occurrence of each letter, it's no more than n/4. | |
| // The objective is to minimize the number of letters in between i and j. | |
| // Naive approach (with some optimization) is O(n^2), if you traverse all possible combinations of i and j. | |
| // Two pointers algorithm will be much better. It will be O(n). | |
| // First, we let j move from right to left, until moving left will be infeasible (one of the letters occur more than n/4 times). | |
| // We need a counter for each letter to do this. | |
| // Then we move i from left to right. For each move, if this move will cause this letter occur more than n/4 times, | |
| // we move j to the right until we reach this letter, than move right one more to keep this letter occur n/4 times. | |
| // During this process, we keep track of the minimum letters in between i and j. | |
| int main() { | |
| int n; | |
| char str[500001]; | |
| scanf("%d %s",&n,str); | |
| int i=0, j=n-1, minl=n; | |
| int cnt[128] = {0}; | |
| while (1) | |
| { | |
| if (j<0 || cnt[str[j]]==n/4) | |
| { | |
| j++; | |
| break; | |
| } | |
| else | |
| { | |
| cnt[str[j]]++; | |
| j--; | |
| } | |
| } | |
| if (j < minl) | |
| minl = j; | |
| for (i=0; i<n; i++) | |
| { | |
| cnt[str[i]]++; | |
| while (j<n && cnt[str[i]] > n/4) | |
| { | |
| cnt[str[j]]--; | |
| j++; | |
| } | |
| if (j==n) | |
| break; | |
| if (j-i-1 < minl) | |
| minl = j-i-1; | |
| } | |
| printf("%d\n",minl); | |
| } |
Comments :
Post a Comment