Finding a substring within a string in C

Question

Given an array of strings I'm trying to find the index on which the given substring starts and ends. Here is my code:

#include <stdio.h>

void find_sub_string(char *str, char *sub){
    int start= 0;
    int end = 0;
    int i=0,j=0;

    while((str[i] != '\0') ){

        if( str[i] == sub[j]){
            if(j == 0){
                start = i;
            }

            i++,j++;

        } else if(str[i] != sub[j]){
            j=0;
            if(str[i] == sub[j]){
                start = i;
                j++,i++;
            } else{
                i++;
            }
        }

        if (sub[j] == '\0'){
            end = i-1;
            printf("The start is: %d ,and end is : %d\n",start,end);
            return;
        }
    }

    printf("The substring %s was not found in string %s\n",sub,str);
    return;
}


int main(){
    char str[] = "internet";
    char sub[] = "net";

    find_sub_string(str,sub);

    return 0;
}

I think the running time is O(n), but I'm not convinced because in the else if statement, I keep going back to the beginning of the substring (j=0) every time I see that str[i] != sub[j]. I'm concerned that it might cause the running time to be not O(n).

P.s This is NOT a homework question. I am just practicing problems.

There's only one loop, and it iterates over the original string. j doesn't matter in here because it doesn't affect how many iterations of the loop are ran. It's O(n). — Colonel Thirty Two
– Colonel Thirty Two, Commented Oct 7, 2014 at 19:07
Might help to see what happens, if you add printf("i=%d j=%d at line %d\n", i, j, __LINE__); to each "then" and "else" branch of the two inner if-else (so add else to the first one). — hyde
– hyde, Commented Oct 7, 2014 at 19:35

David Schwartz · Accepted Answer · 2014-10-07 19:09:12Z

2

The outer loop will run O(n) times since i is always incremented once and is bounded by the size of the string. The number of operations done in each iteration of the loop is a bounded constant since each statement in it can run at most once and each statement does a fixed amount of work. Thus the code is O(n).

answered Oct 7, 2014 at 19:09

David Schwartz

184k18 gold badges229 silver badges292 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Finding a substring within a string in C

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related