strpos in C- how does it work

Understanding strpos in C: A Deep Dive into String Searching

Explore the fundamental concepts behind string searching in C, focusing on how functions like strstr (the C equivalent of PHP's strpos) work, their implementation, and practical usage.

In C programming, finding the occurrence of one string within another is a common task. While languages like PHP offer a direct strpos function, C provides its own set of powerful string manipulation functions, primarily strstr, to achieve similar results. This article will demystify how string searching works in C, focusing on the logic behind strstr and how you can implement your own version for a deeper understanding.

The C Equivalent of strpos: strstr

Unlike PHP's strpos which returns the starting position (index) of the first occurrence of a substring, C's standard library function strstr returns a pointer to the first occurrence of the substring (needle) within the main string (haystack). If the substring is not found, strstr returns a NULL pointer. To get the index, you simply subtract the base address of the haystack from the returned pointer.

#include <stdio.h>
#include <string.h>

int main() {
    const char *haystack = "This is a test string.";
    const char *needle = "test";
    char *result;

    result = strstr(haystack, needle);

    if (result != NULL) {
        printf("Substring found at index: %ld\n", result - haystack);
    } else {
        printf("Substring not found.\n");
    }

    needle = "missing";
    result = strstr(haystack, needle);

    if (result != NULL) {
        printf("Substring found at index: %ld\n", result - haystack);
    } else {
        printf("Substring not found.\n");
    }

    return 0;
}

Using strstr to find a substring and calculate its index.

How strstr Works: A Step-by-Step Breakdown

The underlying mechanism of strstr involves iterating through the haystack string and, at each position, attempting to match the needle string. This is typically done character by character. If a full match is found, the function returns a pointer to the start of that match in the haystack. If a mismatch occurs during the character-by-character comparison, the search in the haystack continues from the next character after the initial potential match point.

flowchart TD
    A[Start `strstr` (haystack, needle)] --> B{Is needle empty?}
    B -- Yes --> C[Return haystack (index 0)]
    B -- No --> D{Is haystack empty?}
    D -- Yes --> E[Return NULL]
    D -- No --> F{Iterate through haystack (ptr_h)}
    F --> G{Current char of haystack matches first char of needle?}
    G -- No --> H[Move to next char in haystack]
    G -- Yes --> I{Attempt full match (ptr_n, ptr_h_temp)}
    I --> J{All chars of needle match?}
    J -- Yes --> K[Return ptr_h (found!)]
    J -- No --> H
    H --> F
    F -- End of haystack --> E

Flowchart illustrating the logic of a basic strstr implementation.

Implementing Your Own my_strstr

To solidify your understanding, let's implement a simplified version of strstr. This custom function, my_strstr, will mimic the behavior of the standard library function, returning a pointer to the first occurrence of the substring or NULL if not found. This implementation uses nested loops: an outer loop to traverse the haystack and an inner loop to compare characters with the needle.

#include <stdio.h>
#include <string.h>

char *my_strstr(const char *haystack, const char *needle) {
    if (!*needle) { // If needle is an empty string, return haystack
        return (char *)haystack;
    }

    while (*haystack) { // Iterate through haystack
        const char *h = haystack;
        const char *n = needle;

        // Attempt to match needle from current position in haystack
        while (*n && *h == *n) {
            h++;
            n++;
        }

        if (!*n) { // If we reached the end of needle, it means a match was found
            return (char *)haystack;
        }

        haystack++; // Move to the next character in haystack
    }

    return NULL; // Substring not found
}

int main() {
    const char *text = "The quick brown fox jumps over the lazy dog.";
    const char *search1 = "fox";
    const char *search2 = "cat";
    const char *search3 = "";

    char *result1 = my_strstr(text, search1);
    if (result1) {
        printf("\"%s\" found at index %ld\n", search1, result1 - text);
    } else {
        printf("\"%s\" not found\n", search1);
    }

    char *result2 = my_strstr(text, search2);
    if (result2) {
        printf("\"%s\" found at index %ld\n", search2, result2 - text);
    } else {
        printf("\"%s\" not found\n", search2);
    }

    char *result3 = my_strstr(text, search3);
    if (result3) {
        printf("Empty string found at index %ld (as per standard behavior)\n", result3 - text);
    } else {
        printf("Empty string not found (should not happen with standard behavior)\n");
    }

    return 0;
}

A custom implementation of my_strstr and its usage.