Substring exists in string in C

Question

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

int main()
{
    char str1[80] = "downtown", str2[20] = "town";
    
    int len1 = 0, len2 = 0, i, j, count;

    len1 = strlen(str1);
    len2 = strlen(str2);

    for (i = 0; i <= len1 - len2; i++) { 
        for (j = i; j < i + len2; j++) {
            count = 1;
            if (str1[j] != str2[j - i]) {
                count = 0;
                break;
            }
        }
        if (count == 1) {
            break;
        }
    }
    if (count == 1) {
        printf("True");
    } else {
        printf("False");
    }
}

In the above code, I'm trying to solve this one without using string functions apart from strlen() which can be replaced with a simple while loop. Is there any other way of checking for consecutive characters like firstly checking if the character is in the string, and if the i index is in the next position and not randomly in the string.

@klutt I remember solving a similar problem but with integers like 500 is in 1500 and remember it being simpler than this one. — EL02
– EL02, Commented Aug 17, 2021 at 11:14
Start by looking for the first character in the sub-string. If you find a match, look at the next character of both strings. If the second character doesn't match, continue searching for the first character in the sub-string, otherwise continue to match the sub-string. — Some programmer dude
– Some programmer dude, Commented Aug 17, 2021 at 11:17
You may find some alternative at String-searching algorithm interesting. — Ted Lyngmo
– Ted Lyngmo, Commented Aug 17, 2021 at 11:18
What is the returned pointer supposed to point at? The start of the found substring in str? — Ted Lyngmo
– Ted Lyngmo, Commented Aug 17, 2021 at 11:42

6 revs, 2 users 70% · Accepted Answer · 2021-08-17 14:41:16Z

3

Here is a very clean way to do it using a function. It assumes that both str and sub are proper C-strings and returns a pointer to first match and NULL if no match.

char *substr(const char *str, const char *sub) {
    if (!*sub)
        return str; // Empty string is substring of all strings

    while (*str) {
        const char *sub1 = sub;
        const char *str1 = str;
        while (*str1++ == *sub1++) {
            if (!*sub1)
                return (char *)str;
        }
        str++;
    }
    return NULL;
}

This function is identical to the standard function strstr(), present in the C Standard library and declared in <string.h>.

edited Aug 17, 2021 at 14:41

community wiki

6 revs, 2 users 70%
klutt

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

4 Comments

EL02 Over a year ago

I'm not that comfortable with pointers, but seems way simpler than mine. Thanks a lot!

EL02 Over a year ago

@klutt oh I thought it was for *a. Just an ignorant question: Why is this line needed :char *tmp = sub? Can't we just use *sub instead of *tmp?

EL02 Over a year ago

@klutt ohhh got it. Thanks!

chux Over a year ago

Try printf("%p\n", substr("ababc", "abc"));.

chqrlie · Accepted Answer · 2021-08-26 21:15:57Z

3

There are some problems in the posted code:

count is uninitialized and only set if the inner loop is reached, which will not be the case if len1 < len2. count should be intialized to 0 to handle this case properly. found would be a more informative name for this variable.
Furthermore, the statement count = 1; should be moved before the inner loop to handle the case of an empty substring.

Here is a modified version:

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

int main() {
    char str1[] = "downtown", str2[] = "town";
    int found = 0;
    size_t len1 = strlen(str1);
    size_t len2 = strlen(str2);

    if (len1 >= len2) {
        for (size_t i = 0; i <= len1 - len2; i++) { 
            found = 1;
            for (size_t j = 0; j < len2; j++) {
                if (str1[i + j] != str2[j]) {
                    found = 0;
                    break;
                }
            }
            if (found) {
                break;
            }
        }
    }
    if (found) {
        printf("True\n");
    } else {
        printf("False\n");
    }
    return 0;
}

edited Aug 26, 2021 at 21:15

answered Aug 17, 2021 at 11:23

chqrlie

152k12 gold badges145 silver badges231 bronze badges

3 Comments

klutt Over a year ago

I would also argue that count is a bad name since it is used as a boolean

chux Over a year ago

Congratulations on 100k!

chqrlie Over a year ago

@klutt: I agree! answer amended.

chux · Accepted Answer · 2021-08-17 12:54:35Z

1

I did not readily see OP's error. See @chqrlie.

Minor: Use size_t i, not int to cope with long strings.

strlen(str1) runs down the entire string, even when not needed, so that is avoided.

Alternative:

Fixed a faulty case in @klutt otherwise good answer.

Added const for greater application.

Return beginning of match on success.

Simplified and test harness added.

I like the needle in a haystack identifiers

char* substr3(const char *haystack, const char *needle) {
  while (*haystack) {
    const char *htmp = haystack;
    const char *ntmp = needle;
    while (*htmp == *ntmp && *htmp) {
      htmp++;
      ntmp++;
    }
    if (!*ntmp) {
      return (char*) haystack;  // Beginning of match
    }
    haystack++;
  }

  return *needle ? NULL : (char *) haystack;
}

int main(void) {
  printf("%s\n", substr3("ababc", "abc"));
  printf("%s\n", substr3("abc", "abc"));
  printf("%s\n", substr3("abd", "ab"));
  printf("%s\n", substr3("abc", ""));
  printf("%s\n", substr3("", ""));

  printf("%p\n", substr3("a", "abc"));
  printf("%p\n", substr3("aba", "abc"));
  printf("%p\n", substr3("x", "ab"));
  printf("%p\n", substr3("aaa", "ab"));
  return 0;
}

Some tighter code

char* substr4(const char *haystack, const char *needle) {
  do {
    const char *htmp = haystack;
    const char *ntmp = needle;
    while (*htmp == *ntmp && *ntmp) {
      htmp++;
      ntmp++;
    }
    if (!*ntmp) {
      return (char*) haystack;  // Beginning of match
    }
  } while (*haystack++);

  return NULL;
}

edited Aug 17, 2021 at 12:54

answered Aug 17, 2021 at 12:29

chux

158k17 gold badges160 silver badges310 bronze badges

1 Comment

chqrlie Over a year ago

I usually frown upon do/while loops, but in this case it seems OK and changing the inner loop to a do/while loop would even save a redundant test :)

ryyker · Accepted Answer · 2021-08-19 15:02:26Z

1

Simple && naive:

char *substr2(char *str, char *sub) {

if (!*sub) return str; // not needed: see the generated code.

for(; *str; str++) {
        size_t pos;
        for(pos=0; str[pos] ; pos++) {
                if (str[pos] != sub[pos]) break;
                }
        if (!sub[pos]) return str;
        }
return NULL;
}

Generally:

if you don't try to outsmart the compiler: you win.
fewer variables: you win
fewer conditions inside the loop: win
try to be smart: you'll lose
when all else fails: use KMP or BM search

edited Aug 19, 2021 at 15:02

ryyker

23.2k3 gold badges46 silver badges96 bronze badges

answered Aug 17, 2021 at 12:51

wildplasser

44.5k9 gold badges72 silver badges116 bronze badges

Collectives™ on Stack Overflow

Substring exists in string in C

4 Answers 4

4 Comments

3 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related