bodia.c IFJ project

#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#define max 10
//strlen()
//strcmp()

/*
 * Gets substring 
 * 
 * @param string s start string
 * @param int i firt position
 * @param int n length of substring
 *
 * @return string sub 
 */
char* substr(char s[], int i, int n) {
   int c = 0;
   char sub[n+1];
 
   while (c < n) {
      sub[c] = s[i+c];
      c++;
   }
   sub[c] = '\0';
   return sub;
}

/*
 * Finds index of search string in parent string
 * 
 * @param string s start string
 * @param string search searching string
 * @param int n length of substring
 *
 * @return 0 if empty search string
 * @return -1 if can`t find search index
 * @return int index of search string
 */
int find(char *s, char *search) {
	int i, j;
	int string_len = strlen(s);
	int search_len = strlen(search);
	if(search_len > string_len) {
		return -1;
	} else if(search_len == 0) {
		return 0;
	}

	int *mem =(int*)malloc(search_len*sizeof(int)); //set dynamic memory

	//prefix function
	mem[0]=0;
	for(i=1,j=0; i<search_len; i++) {
		while(j>0 && search[j]!=search[i]) {
			j = mem[j-1];
		}

		if(search[j]==search[i]) {
			j++;
		}
		mem[i]=j;
	}
	

	//search substring index in start string
	for(i=0,j=0; i<string_len; i++) {
		while(j>0 && search[j]!=s[i]) {
			j=mem[j-1];
		}

		if(search[j]==s[i]) {
            j++;
		}
		
		if (j==search_len) {
			free (mem); //clean memory
            return i-j+1;
        }
	}

    free (mem); //clean memory

	return -1;
}

char a[10] = "adasdasdds";
// int a[10] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
int b[10];

void merging(int low, int mid, int high) {
   int l1, l2, i;

   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   
   while(l1 <= mid)    
      b[i++] = a[l1++];

   while(l2 <= high)   
      b[i++] = a[l2++];

   for(i = low; i <= high; i++)
      a[i] = b[i];
}

void sort(int low, int high) {
   int mid;
   
   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   } else { 
      return;
   }   
}



int main() 
{
   //> To test function substr() - uncomment and test
	   // char string[1000];
	   // int position, length;
	 
	   // printf("Write a string which use to gets a substring\n");
	   // gets(string);
	 
	   // printf("Write the position of substring\n");
	   // scanf("%d", &position);
	   // printf("Write the length of substring\n");
	   // scanf("%d", &length);
	 
	   // printf("%s\n", substr(string, position, length));
   //<

   //> To test function find() - uncomment and test
	   // char string[] = "atrd sdfsdf dsf";
	   // char search_str[] = "sdf";
	   // int search_str_index;

	   // search_str_index = find(string, search_str);
	   // if (search_str_index >= 0) {
		  //  printf("Index of search string: %d\n", search_str_index);
	   // } else {
		  //  printf("Not find!!!\n");
	   // }
   //<




	   int i;

   printf("List before sorting\n");
   
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);

   sort(0, max);

   printf("\nList after sorting\n");
   
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);

   return 0;
}