Own vesions of String library functions

Write your own implementations for following string library functions

1.strstr()
2.strcpy()
3.strcmp()
4.substr()
5.strdup()
6.strlen()
7.strcat()
8.strchr()
9.toUpper() & isUpper()

Set-2
1.strncmp()
2.strncat()
3.strncpy()
4.strrchr()

strcpy()

Method 1:
char *mystrcpy(char *dst, const char *src)
{
  char *ptr;
  ptr = dst;
  while(*dst++=*src++);
  return(ptr);
}
Method 2:
char *my_strcpy(char dest[], const char source[])
{
  int i = 0;
  while (source[i] != '\0')
  {
    dest[i] = source[i];
    i++;
  }
  dest[i] = '\0';
  return(dest);
}
NOTE:
1.The strcpy function copies src, including the terminating null character, to the location specified by dst. No overflow checking is performed when strings are copied or appended. The behavior of strcpy is undefined if the source and destination strings overlap. It returns the destination string. No return value is reserved to indicate an error.

2.Note that the prototype of strcpy as per the C standards is
 char *strcpy(char *dst, const char *src);
 Notice the const for the source, which signifies that the function must not change the source string in anyway!.
strncpy()

char * strncpy ( char * destination, const char * source, size_t num );

Copy characters from string

Copies the first num characters of source to destination. If the end of the source C string (which is signaled by a null-character) is found before num characters have been copied, destination is padded with zeros until a total of num characters have been written to it.

No null-character is implicitly appended to the end of destination, so destination will only be null-terminated if the length of the C string in source is less than num.
char *(strncpy)(char *s1, const char *s2, size_t  n)
 {
     char *dst = s1;
     const char *src = s2;
     while (n > 0) {
         n--;
         if ((*dst++ = *src++) == '\0') {
             memset(dst, '\0', n);
             break;
         }
     }
     return s1;
 }

substr():

void mySubstr(char *dest, char *src, int position, int length)
{
  while(length > 0)
  {
    *dest = *(src+position);
    dest++;
    src++;
    length--;
  }
}
Alternative:
char *substr(const char *pstr, int start, int numchars)
{
char *pnew = (char *)malloc(numchars+1);
strncpy(pnew, pstr + start, numchars);
pnew[numchars] = '\0';
return pnew;
}

Note:
substr() is used to copy a substring starting from position upto length

strdup():

char *mystrdup(char *s)
{
    char *result = (char*)malloc(strlen(s) + 1);
    if (result == (char*)0)
             {return (char*)0;}
    strcpy(result, s);
    return result;
}
strcmp()

int (strcmp)(const char *s1, const char *s2)
 {
     unsigned char uc1, uc2;
     /* Move s1 and s2 to the first differing characters 
        in each string, or the ends of the strings if they
        are identical.  */
     while (*s1 != '\0' && *s1 == *s2) {
         s1++;
         s2++;
     }
     /* Compare the characters as unsigned char and
        return the difference.  */
     uc1 = (*(unsigned char *) s1);
     uc2 = (*(unsigned char *) s2);
     return ((uc1 < uc2) ? -1 : (uc1 > uc2));
 }

Note:

strcmp(str1,str2) returns a -ve number if str1 is alphabetically less than str2, 0 if both are equal and +ve if str1 is alphabetically above str2.The prototype of strcmp() is

 int strcmp( const char *string1, const char *string2 );

strncmp()
int (strncmp)(const char *s1, const char *s2, size_t  n)
 {
     unsigned char uc1, uc2;
     if (n == 0)
         return 0;
     while (n-- > 0 && *s1 == *s2)
    {
         if (n == 0 || *s1 == '\0')
             return 0;
         s1++;
         s2++;
     }
     uc1 = (*(unsigned char *) s1);
     uc2 = (*(unsigned char *) s2);
     return ((uc1 < uc2) ? -1 : (uc1 > uc2));
 }

strlen():

Method 1:
int my_strlen(char *string)
{
  int length;
  for (length = 0; *string != '\0', string++)
  {
    length++;
  }
  return(length);
}
Method 2: Pointer difference
int my_strlen(char *s)
{
  char *p=s;
  while(*p!='\0')
    p++;
  return(p-s);
}
Note:
The prototype of the strlen() function is
size_t strlen(const char *string);

strrchr()

const char * strchr ( const char * str, int character );
      char * strchr (       char * str, int character );

Locate first occurrence of character in string
Returns a pointer to the first occurrence of character in the C string str.
The terminating null-character is considered part of the C string. Therefore, it can also be located to retrieve a pointer to the end of a string.

char *(strrchr)(const char *s, int c)
 {
     const char *last = NULL;
         if (c == '\0')
         return strchr(s, c);
     while ((s = strchr(s, c)) != NULL) {
         last = s;
         s++;
     }
     return (char *) last;
 }

strcat():

char *myStrcat(char *s, const char *t)
{
    char *p = s;
    if (s == NULL || t == NULL)
        return s;   /* we need not have to do anything */
    while (*s)
        s++;
    while (*s++ = *t++);
    return p;
}
strncat()

 char *(strncat)(char *s1, const char *s2, size_t n)
 {
     char *s = s1;
     while (*s != '\0')
         s++;
     while (n != 0 && (*s = *s2++) != '\0') {
         n--;
         s++;
     }
     if (*s != '\0')
         *s = '\0';
     return s1;
 }

toUpper():
int toUpper(int ch)
{
    if(ch>='a' && c<='z')
        return('A' + ch - 'a');
    else
        return(ch);
}

isUpper():
int isUpper(int ch)
{
    if(ch>='A' && ch <='Z')
       return(1); //Yes, its upper!
    else
       return(0); // No, its lower!
}
Note:
Another way to do this conversion is to maintain a correspondance between the upper and lower case alphabets. The program below does that. This frees us from the fact that these alphabets have a corresponding integer values.

#include <string.h>
#define UPPER   "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define LOWER   "abcdefghijklmnopqrstuvwxyz"

int toUpper(int c)
{
    const char *upper;
    const char *const lower = LOWER;
       
    // Get the position of the lower case alphabet in the LOWER string using the strchr() function ..
    upper = ( ((CHAR_MAX >= c)&&(c > '\0')) ? strchr(lower, c) : NULL);

      // Now return the corresponding alphabet at that position in the UPPER string ..
    return((upper != NULL)?UPPER[upper - lower] : c);
}

Useful Links:
http://en.wikibooks.org/wiki/C_Programming/Strings

Zigzag Conversion of String

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

http://k2code.blogspot.in/2016/03/convert-string-to-zigzag-bottom-up.html
http://n00tc0d3r.blogspot.in/2013/06/zigzag-conversion.html

Print shortest path to print a string on screen

Given a screen containing alphabets from A-Z, we can go from one character to another characters using a remote. The remote contains left, right, top and bottom keys.
http://www.geeksforgeeks.org/print-shortest-path-print-string-screen/

Find The Longest Sequence Of Prefix Shared By All The Words In A String

Write an algo­rithm to find The Longest Sequence Of Pre­fix Shared By All The Words In A String. This prob­lem is bit tricky, it looks dif­fi­cult but actu­ally it is sim­ple problem.

http://algorithms.tutorialhorizon.com/find-the-longest-sequence-of-prefix-shared-by-all-the-words-in-a-string/

Storage of Strings in C

How readonly & dynamically allocated strings are stored in C

In C, a string can be referred either using a character pointer or as a character array.

Strings as character arrays





char str[4] = "GfG"; /*One extra for string terminator*/

/*    OR    */

char str[4] = {‘G’, ‘f’, ‘G’, '\0'}; /* '\0' is string terminator */






When strings are declared as character arrays, they are stored like other types of arrays in C. For example, if str[] is an auto variable then string is stored in stack segment, if it’s a global or static variable then stored in data segment, etc.

Strings using character pointers

Using character pointer strings can be stored in two ways:

1) Read only string in a shared segment.

When string value is directly assigned to a pointer, it’s stored in a read only block(generally in data segment) that is shared among functions





char *str  =  "GfG";






In the above line “GfG” is stored in a shared read only location, but pointer str is stored in a read-write memory. You can change str to point something else but cannot change value at present str. So this kind of string should only be used when we don’t want to modify string at a later stage in program.



And also the above should be declared as


const char *p = "Hello";So the compiler will throw an error if you try to modify it.



2) Dynamically allocated in heap segment.

Strings are stored like other dynamically allocated things in C and can be shared among functions.





char *str;

int size = 4; /*one extra for ‘\0’*/

str = (char *)malloc(sizeof(char)*size);

*(str+0) = 'G';

*(str+1) = 'f';

*(str+2) = 'G';

*(str+3) = '\0';






Example 1 (Try to modify string) 

The below program may crash (gives segmentation fault error) because the line *(str+1) = ‘n’ tries to write a read only memory.





int main()

{

 char *str;

 str = "GfG";     /* Stored in read only part of data segment */

 *(str+1) = 'n'; /* Problem:  trying to modify read only memory */

 getchar();

 return 0;

}






str is a pointer stored on the stack. It gets initialized to point to the literal string "abc". That literal string is going to be stored in the data section of your compiled executable and gets loaded into memory when your program is loaded. That section of memory is read-only, so when you try and modify the data pointed to by str, you get an access violation.


char* str = malloc(sizeof(char) * 4);
strcpy(str, "abc");


Here, str is the same stack pointer.This time, it is initialized to point to a 4-character block of memory on the heap that you can both read and write. At first that block of memory is uninitialized and can contain anything. strcpy reads the block of read-only memory where "abc" is stored, and copies it into the block of read-write memory that str points to. Note that setting str[3] = '\0' is redundant, since strcpy does that already.

As an aside, if you are working in visual studio, use strcpy_s instead to make sure you don't overwrite your buffer if the string being copied is longer than you expected.

Here str is now an array allocated on the stack. The compiler will sized it exactly fit the string literal used to initialize it (including the NULL terminator). The stack memory is read-write so you can modify the values in the array however you want.





Below program works perfectly fine as str[] is stored in writable stack segment.





int main()

{

 char str[] = "GfG";  /* Stored in stack segment like other auto variables */

 *(str+1) = 'n';   /* No problem: String is now GnG */

 getchar();

 return 0;

}






Below program also works perfectly fine as data at str is stored in writable heap segment.





int main()

{

  int size = 4;



  /* Stored in heap segment like other dynamically allocated things */

  char *str = (char *)malloc(sizeof(char)*size);

  *(str+0) = 'G';

  *(str+1) = 'f';

  *(str+2) = 'G';

  *(str+3) = '\0';

  *(str+1) = 'n';  /* No problem: String is now GnG */

   getchar();

   return 0;

}






Example 2 (Try to return string from a function) The below program works perfectly fine as the string is stored in a shared segment and data stored remains there even after return of getString()





char *getString()

{

  char *str = "GfG"; /* Stored in read only part of shared segment */



  /* No problem: remains at address str after getString() returns*/

  return str;

}     



int main()

{

  printf("%s", getString());

  getchar();

  return 0;

}






The below program alse works perfectly fine as the string is stored in heap segment and data stored in heap segment persists even after return of getString()





char *getString()

{

  int size = 4;

  char *str = (char *)malloc(sizeof(char)*size); /*Stored in heap segment*/

  *(str+0) = 'G';

  *(str+1) = 'f';

  *(str+2) = 'G';

  *(str+3) = '\0';  



  /* No problem: string remains at str after getString() returns */

  return str;

}

int main()

{

  printf("%s", getString());

  getchar();

  return 0;

}






But, the below program may print some garbage data as string is stored in stack frame of function getString() and data may not be there after getString() returns.






char *getString()



{



  char str[] = "GfG"; /* Stored in stack segment */





  /* Problem: string may not be present after getSting() returns */



  return str;



}



int main()



{



  printf("%s", getString());



  getchar();



  return 0;



}