Finding a substring

Question

I have to write some code for an assignment which finds a substring within a string.

Here is my code, and I added comments:

// the target is the substring that we want to find in the source string // m is the length of the target, and n is the length of the source int contains(char target[], int m, char source[], int n) { int flag = 0; // the source originally does not contain the target int i; // go through each character of the source string for(i = 0; i < n; i++) { int targetIndex = 0; int j; // check if the preceding characters of the source string are a substring // that matches the target string for(j = i; j < n && targetIndex < m; j++) { if(target[targetIndex] == source[j]) { flag = 1; targetIndex += 1; } else { flag = 0; // a letter does not match break; } } } return flag;

}

So when I test this method, I always get 0 returned and I can't understand why.
If I try int i = contains("potatoes", 8, "toes", 4); it gives 0.
I've tried putting some print statements to see what character it matches, and it seems it only finds the first letter "t".

Since this is basically just strstr(), I suggest you have a look at an implementation, e. g. the one in glibc. — user529758
– user529758, Commented Oct 12, 2013 at 14:52

ugoren · Accepted Answer · 2013-10-12 14:49:50Z

You need to break the outer for when you have a match.

The way your code works, you may find a match, then run the outer loop again and "forget" about it.

Rahul Tripathi · Accepted Answer · 2013-10-16 12:06:24Z

Try like this:

for(i = 0; i < n; i++) { int targetIndex = 0; int j; // check if the preceding characters of the source string are a substring // that matches the target string for(j = i; j < n && targetIndex < m; j++) { if(target[targetIndex] == source[j]) { flag = 1; targetIndex += 1; } else { flag = 0; // a letter does not match break; } } if(flag == 1) { break; } }

You can instead try with the strstr function of C which will make things easier for you.

Example:

char *x= "Find the substring in this string"; char *y= "substring"; if(strstr(x, y) != NULL) { return true; }

@GrijeshChauhan:- Thanks Grijesh for pointing that. Updated my answer. But I think the second option is more better which OP must adopt!
now it is good but actaully you don't need else{..} in inner for loop just set flag = 0 before outer break loop, Additionally don't use break instead return i; at outer if.
One more point you don't need extra flag variable just check whether j > i + m in if in outer for loop... Actually the code written by OP can improve much better.

Siddhartha Ghosh · Accepted Answer · 2013-10-12 15:07:27Z

A little modification to your code with explanatory comments.

// the target is the substring that we want to find in the source string // m is the length of the target, and n is the length of the source int contains(char target[], int m, char source[], int n) { int flag = 0; // the source originally does not contain the target int i; // go through each character of the source string for(i = 0; i < n; i++) { int targetIndex = 0; int j; // check if the preceding characters of the source string are a substring // that matches the target string for(j = i; j < n && targetIndex < m; j++) { if(target[targetIndex] == source[j]) { targetIndex += 1; if(targetIndex == m) { // the 'target' has been fully found flag = 1; break; } } else { break; } } if(flag == 1) // 'target' is already found, no need to search further { break; } } return flag; }

Break both the inner and outer loop when the substring is fully found.

EDITED: Also, instead of int i = contains("potatoes", 8, "toes", 4); , it should be int i = contains("toes", 4, "potatoes", 8); -- as per your function description.

Collectives™ on Stack Overflow

Finding a substring

3 Answers 3

Comments

4 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

4 Comments

Comments

Related