Skip to main content
Code Review

Return to Answer

added 1 character in body
Source Link
Jerry Coffin
Jerry Coffin
  • 33.6k
  • 4
  • 75
  • 143
char const *check(char const *s) {
    if (s)
        return s;
    return "[NULL POINTER]";
}

#define elements(arr) (sizeof(arr)/sizeof(arr[0]))

int main() {
    char input1[] = "This is some input for the function";

    // tests: match middle, non-match, match begin, match end, empty string
    char const *tests[] = { "for", "was", "This", "ion", "" };

    for (int isize_t = 0; i < elements(tests); i++)
        printf("%s\n", check(find_substr(input1, tests[i])));

    printf("%s\n", check(find_substr("the", "this is a longer string")));
}

char const *check(char const *s) {
    if (s)
        return s;
    return "[NULL POINTER]";
}

#define elements(arr) (sizeof(arr)/sizeof(arr[0]))

int main() {
    char input1[] = "This is some input for the function";

    // tests: match middle, non-match, match begin, match end, empty string
    char const *tests[] = { "for", "was", "This", "ion", "" };

    for (int i = 0; i < elements(tests); i++)
        printf("%s\n", check(find_substr(input1, tests[i])));

    printf("%s\n", check(find_substr("the", "this is a longer string")));
}

char const *check(char const *s) {
    if (s)
        return s;
    return "[NULL POINTER]";
}

#define elements(arr) (sizeof(arr)/sizeof(arr[0]))

int main() {
    char input1[] = "This is some input for the function";

    // tests: match middle, non-match, match begin, match end, empty string
    char const *tests[] = { "for", "was", "This", "ion", "" };

    for (size_t = 0; i < elements(tests); i++)
        printf("%s\n", check(find_substr(input1, tests[i])));

    printf("%s\n", check(find_substr("the", "this is a longer string")));
}
deleted 22 characters in body
Source Link
Jerry Coffin
Jerry Coffin
  • 33.6k
  • 4
  • 75
  • 143
size_t length(char const *s) {
    size_t i;
    for (size_ti i=0;= 0; s[i]; i++)
        ;
    return i;
}

bool match(char const *a, char const *b) { 
     while (*b)
         if (*a++ != *b++)
             return false;
     return true;
}

char const *check(char const *s) {
    if (s)
        return s;
    return "[NULL POINTER]";
}

#define elements(arr) (sizeof(arr)/sizeof(arr[0]))

int main() {
    char input1[] = "This is some input for the function";

    // tests: match middle, non-match, match begin, match end, matchempty beginstring
    char const *tests[] = { "for", "was", "This", "ion", "" };

    for (int i = 0; i < elements(tests); i++)
        printf("%s\n", check(find_substr(input1, tests[i])));

    printf("%s\n", check(find_substr("the", "this is a longer string")));
}

size_t length(char const *s) { 
    for (size_t i=0; s[i]; i++)
        ;
    return i;
}

bool match(char const *a, char const *b) { 
     while (*b)
         if (*a++ != *b++)
             return false;
     return true;
}

char const *check(char const *s) {
    if (s)
        return s;
    return "[NULL POINTER]";
}

#define elements(arr) (sizeof(arr)/sizeof(arr[0]))

int main() {
    char input1[] = "This is some input for the function";

    // tests: match middle, non-match, match begin, match end, match begin
    char const *tests[] = { "for", "was", "This", "ion", "" };

    for (int i = 0; i < elements(tests); i++)
        printf("%s\n", check(find_substr(input1, tests[i])));

    printf("%s\n", check(find_substr("the", "this is a longer string")));
}

size_t length(char const *s) {
    size_t i;
    for (i = 0; s[i]; i++)
        ;
    return i;
}

bool match(char const *a, char const *b) {
    while (*b)
        if (*a++ != *b++)
            return false;
    return true;
}

char const *check(char const *s) {
    if (s)
        return s;
    return "[NULL POINTER]";
}

#define elements(arr) (sizeof(arr)/sizeof(arr[0]))

int main() {
    char input1[] = "This is some input for the function";

    // tests: match middle, non-match, match begin, match end, empty string
    char const *tests[] = { "for", "was", "This", "ion", "" };

    for (int i = 0; i < elements(tests); i++)
        printf("%s\n", check(find_substr(input1, tests[i])));

    printf("%s\n", check(find_substr("the", "this is a longer string")));
}
Source Link
Jerry Coffin
Jerry Coffin
  • 33.6k
  • 4
  • 75
  • 143

This strikes me as somewhat...clumsy code that makes the job more difficult than truly necessary.

I'd break the task up into pieces, something like:

for every candidate position in the haystack
    if the needle matches at this point
        return success at this point
return failure

So that leaves us with two subordinate tasks:

  1. Figure out the candidate positions
  2. Check for a match starting at a specified point

The first is pretty simple: the candidate positions are the beginning of the haystack through the length of the haystack minus the length of the needle (and if the needle is larger than the haystack, it can't possibly match).

The second is even simpler: step through both strings, and if they don't match at a given point, return indicating failure. If (and only if) you reach the end of the second without a mismatch, return indicating success.

So let's write some code for that:

size_t length(char const *s) { 
    for (size_t i=0; s[i]; i++)
        ;
    return i;
}

bool match(char const *a, char const *b) { 
     while (*b)
         if (*a++ != *b++)
             return false;
     return true;
}

Then we can do the function itself:

char const *find_substr(char const *haystack, char const *needle) {
    size_t len1 = length(haystack);
    size_t len2 = length(needle);

    for (size_t i = 0; i+len2<=len1; i++)
        if (match(haystack + i, needle))
            return haystack + i;
    return NULL;
}

Then we probably want a bit of test code to verify that it works to at least some degree under some circumstances:

char const *check(char const *s) {
    if (s)
        return s;
    return "[NULL POINTER]";
}

#define elements(arr) (sizeof(arr)/sizeof(arr[0]))

int main() {
    char input1[] = "This is some input for the function";

    // tests: match middle, non-match, match begin, match end, match begin
    char const *tests[] = { "for", "was", "This", "ion", "" };

    for (int i = 0; i < elements(tests); i++)
        printf("%s\n", check(find_substr(input1, tests[i])));

    printf("%s\n", check(find_substr("the", "this is a longer string")));
}

There are certainly other ways the job could be done, but that seems to me like it's at least a reasonable way to implement what's probably the simplest (and most naive) one.