w3resource

C Exercises: Find the index of the first occurrence of a given string within another given string

C Programming Practice: Exercise-14 with Solution

Write a C programming to find the index of the first occurrence of a given string within another given string. If not found return -1.

C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int sub_str_func(char *main_str, char *sub_str)
{
    if (main_str == NULL || sub_str == NULL) {
        return -1;
    }

    int main_len = strlen(main_str);
    int sub_len = strlen(sub_str);

    if (main_len < sub_len) {
        return -1;
    }

    if (sub_len == 0) {
        return 0;
    }

    int i, j;
    int bad_steps[128];
    for (i = 0; i < 128; i++) {
        bad_steps[i] = sub_len;
    }
    for (i = 0; i < sub_len; i++) {
        bad_steps[sub_str[i]] = sub_len - 1 - i;
    }
    int *good_steps = malloc(sub_len * sizeof(int));
    for (i = 0; i < sub_len; i++) {
        good_steps[i] = sub_len;
        for (j = i - 1; j >= 0; j--) {
            if (!memcmp(sub_str + i, sub_str + j, sub_len - i)) {
                good_steps[i] = i - j;
                break;
            }
        }
    }

    char *p = main_str + sub_len - 1;
    char *q = sub_str + sub_len - 1;
    char *r = p;
    while (p - main_str < main_len) {
        int step = 0;
        for (i = 1; i <= sub_len && *p == *q; i++) {
            if (q == sub_str) {
                return p - main_str;
            }
            if (good_steps[sub_len - i] > step) {
                step = good_steps[sub_len - i];
            }
            p--;
            q--;
        }

        if (i == 1 && bad_steps[*p] > step) {
            step = bad_steps[*p];
        }
        r += step;
        p = r;
        q = sub_str + sub_len - 1;
    }

    return -1;
}

static int strStr(char *main_str, char *sub_str)
{
    unsigned int main_len = strlen(main_str);
    unsigned int sub_len = strlen(sub_str);

    if (sub_len == 0) {
        return 0;
    }

    int i, j;
    for (i = 0; i < main_len; i++) {
        int found = 1;
        if (main_str[i] == sub_str[0]) {
	    for (j = 1; j < sub_len; j++) {
                if (i + j < main_len) {
                    if (main_str[i + j] != sub_str[j]) {
                        found = 0;
                        break;
                    }
                } else {
                    return -1;
                }
	    }
	    if (found) {
    		return i;
    	    }
	}
    }

    return -1;
}

int main(void)
{
   	char main_str[] = "w3resource.com";
	char sub_str[] = "source";
	printf("\nMain string: %s",main_str);
	printf("\nSubstring searched in main string: %s",sub_str);
    printf("\nStarting position of the substring in the main string: %d", sub_str_func(main_str, sub_str));
    return 0;
}

Sample Output:

Main string: w3resource.com
Substring searched in main string: source
Starting position of the substring in the main string: 4

Pictorial Presentation:

C Programming: Find the index of the first occurrence of a given string within another given string.

Flowchart: 1

C Programming Flowchart: Find the index of the first occurence of a given string within another given string

Flowchart: 2

C Programming Flowchart: Find the index of the first occurence of a given string within another given string

C Programming Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C programming to remove all instances of a given value in a given array of integers and return the length of the new array.
Next: Write a C programming to divide two given integers without using multiplication, division and mod operator. Return the quotient after dividing.

What is the difficulty level of this exercise?



C Programming: Tips of the Day

The tilde operator in C:

The ~ operator is bitwise NOT, it inverts the bits in a binary number:

NOT 011100
  = 100011

Ref : https://bit.ly/3DR1N24