String Handling & Advanced C: Functions, Libraries & Efficiency

TAKEAWAYS

• String functions (strlen, strcpy, strcat, strcmp) are library functions in <string.h> that operate on null-terminated character arrays.
• Custom string operations (reverse, concatenate, search) require manual loops and pointer arithmetic—no built-in functions allowed in exams.
• Dynamic string allocation (malloc, realloc) enables resizable strings (e.g., user input of unknown length).
• File I/O with strings (fgets, fputs) handles text processing (e.g., log files, CSV data).
• Time/space complexity (O(n) for linear scans, O(1) for direct access) matters for scalability (e.g., Daraz’s order processing).
• Edge cases (empty strings, \0, overflow) are common exam pitfalls—always validate inputs.

1. String Basics: Representation and Initialization

Strings in C are null-terminated character arrays. The null terminator '\0' marks the end.

char str1[] = "Hello";  // Array with implicit '\0'
char str2[6] = {'H', 'e', 'l', 'l', 'o', '\0'};  // Explicit '\0'
char str3[6] = "Hello";  // Must fit 5 chars + '\0'
char *str4 = "Hello";    // Pointer to string literal (read-only)

Visual: String in Memory

+---+---+---+---+---+---+
| 'H'| 'e'| 'l'| 'l'| 'o'| '\0' |
+---+---+---+---+---+---+
   ^               ^
   |               |
str1[0]          str1[5]

Exam Tip: Always declare arrays with 1 extra space for '\0' when initializing manually.

2. String Functions from <string.h>

The C standard library provides predefined functions for common operations. These are not allowed in custom programs unless explicitly permitted in the question.

Visual: strcpy Operation

graph LR
    A["Source: 'Hello'"] -->|"strcpy"| B["Destination: '-----'"]
    B --> C["Destination: 'Hello'"]

Worked Example: Safe String Copy

#include <string.h>
void safe_copy(char *dest, const char *src, size_t size) {
    strncpy(dest, src, size - 1);  // Leave space for '\0'
    dest[size - 1] = '\0';
}

Trace:

Real-World: Khalti’s transaction IDs Khalti generates unique 12-character alphanumeric IDs for payments. Internally, it uses strcpy to copy user-provided prefixes (e.g., "KH-"), then appends a random suffix. Edge case: If a user enters a string longer than 12 chars, strncpy prevents buffer overflow.

3. Custom String Operations (Exam Focus)

Since exams restrict library functions, you must implement operations manually.

A. String Length Without strlen

int my_strlen(const char *s) {
    int len = 0;
    while (s[len] != '\0') len++;
    return len;
}

Trace:

Visual: Loop Execution

flowchart TD
    A["Start: s = 'Hi\0'"] --> B["len = 0"]
    B --> C["Check s[0] ('H') != '\0'"]
    C -->|"Yes"| D["len = 1"]
    D --> E["Check s[1] ('i') != '\0'"]
    E -->|"Yes"| F["len = 2"]
    F --> G["Check s[2] ('\0') != '\0'"]
    G -->|"No"| H["Return 2"]

B. Reverse a String (Past Exam Question)

void reverse_string(char *s) {
    int len = my_strlen(s);
    for (int i = 0; i < len / 2; i++) {
        char temp = s[i];
        s[i] = s[len - 1 - i];
        s[len - 1 - i] = temp;
    }
}

Trace for "abc":

Visual: String Reversal Steps

graph LR
    A["Initial: 'a', 'b', 'c', '\0'"] --> B["After i=0: 'c', 'b', 'a', '\0'"]
    B --> C["After i=1: 'c', 'b', 'a', '\0' (no change)"]

Real-World: Ncell’s SMS Reversal Trick Ncell’s old SMS-based services (e.g., balance checks) sometimes reversed strings to obfuscate commands. For example, sending "?bal" might be stored as "lab?" internally, then reversed before processing. This avoids simple string matching attacks.

4. Dynamic String Allocation

Static strings (char str[100]) have fixed sizes. For user input of unknown length, use dynamic allocation:

char *read_dynamic_string() {
    char *str = NULL;
    int size = 10, len = 0;
    str = (char *)malloc(size * sizeof(char));
    if (!str) return NULL;

    char c = getchar();
    while (c != '\n' && c != EOF) {
        if (len + 1 >= size) {
            size *= 2;
            str = (char *)realloc(str, size * sizeof(char));
        }
        str[len++] = c;
        c = getchar();
    }
    str[len] = '\0';
    return str;
}

Trace for Input "Hello":

Visual: Memory Growth

sequenceDiagram
    participant User as User Input
    participant Str as String Buffer
    User->>Str: 'H' (len=0)
    User->>Str: 'e' (len=1)
    User->>Str: 'l' (len=2)
    User->>Str: 'l' (len=3)
    User->>Str: 'o' (len=4)
    Str->>Str: realloc (size=10)
    User->>Str: '\n' (terminate)

Real-World: Daraz’s Order Processing Daraz’s order IDs (e.g., ORD123456789) are dynamically generated and stored in resizable buffers. If a user enters a long product description, Daraz uses realloc to expand the string storage without crashing.

5. File Handling with Strings

Files are streams of characters. Use fgets/fputs for text files:

#include <stdio.h>
void read_write_file() {
    FILE *fp = fopen("data.txt", "r+");
    if (!fp) {
        perror("Error");
        return;
    }

    char line[100];
    while (fgets(line, sizeof(line), fp)) {
        printf("Read: %s", line);
        fputs("Processed: ", fp);  // Append to file
        fputs(line, fp);
    }
    fclose(fp);
}

Trace for data.txt with "Hello\nWorld":

Visual: File I/O Flow

flowchart TD
    A["Open File"] --> B["Read Line with fgets"]
    B -->|"Hello\n"| C["Process Line"]
    C --> D["Write to File with fputs"]
    D --> B

Real-World: eSewa’s Transaction Logs eSewa stores transaction records (e.g., "2023-10-01, USER123, 500") in CSV files. Their backend uses fgets to read each line, then fputs to append processed data (e.g., "2023-10-01, USER123, 500, SUCCESS").

6. String Search and Substitution

A. Linear Search in a String

int str_search(const char *str, char ch) {
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == ch) return i;
    }
    return -1;
}

Trace for "Nepal" searching 'p':

B. Replace All Occurrences

void replace_char(char *str, char old, char new) {
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == old) str[i] = new;
    }
}

Trace for "book" replacing 'o' with 'a':

Real-World: NTC’s License Plate Processing NTC’s automated license plate readers use string search to:

1. Find digits (e.g., "KA-05-AB1234" → search for '0'-'9').
2. Replace invalid characters (e.g., "KA-05@AB1234" → replace '@' with 'A').

7. Time and Space Complexity

Visual: Complexity Comparison

pie
    title String Operation Complexities
    "O(1)" : 0.1
    "O(n)" : 0.9

Real-World: Pathao’s Ride Matching Pathao’s algorithm matches riders to drivers by:

1. Searching a string of available drivers (O(n) per query).
2. Using hash tables (for O(1) lookups) to store driver locations by geohash strings.

8. Edge Cases and Validation

Always handle:

1. Empty strings ("" or NULL).
2. Buffer overflows (e.g., strcpy(dest, src) where dest is too small).
3. Non-null-terminated strings (undefined behavior).

Example: Safe Concatenation

void safe_concat(char *dest, const char *src, size_t dest_size) {
    int dest_len = my_strlen(dest);
    int src_len = my_strlen(src);
    if (dest_len + src_len + 1 >= dest_size) {
        printf("Error: Buffer overflow!\n");
        return;
    }
    for (int i = 0; src[i] != '\0'; i++) {
        dest[dest_len + i] = src[i];
    }
    dest[dest_len + src_len] = '\0';
}

Trace for dest="Hi", src="!", dest_size=3:

In the Real World

1. Khalti’s Payment IDs

   • Idea Used: String concatenation (strcat) and dynamic allocation.
   • How: Khalti generates IDs like "KH-123456789" by:
     • Starting with a static prefix ("KH-").
     • Appending a random 9-digit number (converted to string).
     • Using realloc if the user-provided merchant ID is longer than expected.

2. Daraz’s Order Queue

   • Idea Used: String search (strstr) and file I/O (fgets/fputs).
   • How: Daraz’s backend:
     • Reads orders from a CSV file (fgets).
     • Searches for "STATUS: PENDING" using strstr.
     • Updates status to "STATUS: SHIPPED" via fputs.

3. Ncell’s SMS Keyword Processing

   • Idea Used: String reversal and character replacement.
   • How: Old Ncell services reversed user inputs (e.g., "?bal" → "lab?") to:
     • Obfuscate commands (prevent brute-force attacks).
     • Use simple string matching (e.g., if reversed string starts with "lab", return balance).

Exam Tip

1. For reversal programs:

   • Always use two pointers (one from start, one from end) to swap characters.
   • Edge case: Empty string or single character (no swap needed).

2. For dynamic strings:

   • Initialize with a small buffer (e.g., 10 chars) and double size when full.
   • Free memory (free(str)) to avoid leaks.

3. File handling:

   • Check fopen return value (exams deduct for missing checks).
   • Use fgets with size to prevent overflows.

4. String functions:

   • Never use strcpy/strcat without bounds checking in exams.
   • Prefer strncpy/strncat for safety.

5. Complexity questions:

   • Count operations: Each while loop iteration is O(1), but n iterations → O(n).
   • Example: Reversing a string requires n/2 swaps → O(n).

Practice Question: Write a program to read a sentence from the user, replace all vowels with '*', and write the result to a file output.txt. Handle edge cases (empty input, no vowels).