Substring exists in string in C

user_14826884 0
Viewed 166
#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.

function c string
4 Answers

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>.

user_66994330

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;
}
user_45932670

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;
}
user_24103590

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
user_9059020
Related