logo CodeStepByStep logo

locate_overlap

Language/Type: C strings pointers return
Author: Cynthia Lee (on 2016/10/05)

Write a function locate_overlap that takes two string "fragments" left_frag and right_frag (as char*) and an int pointer as parameters, and attempts to see how they could overlap (this problem is related to some DNA sequencing problems). Specifically, the function determines how the right_frag could be merged onto the left_frag, possibly with right_frag spilling off the end of left_frag (hence the names left and right).

The return value is the maximal amount of overlap found.

The overlap parameter is in effect a "pass by reference" for the purpose of outputing the location where right_frag should be placed. Before returning, locate_overlap should set the value pointed to by overlap to be the offset where right_frag fits (i.e., right frag fits starting at left_frag[offset]). If no overlap is found, then the value pointed to by offset is set to strlen(left_frag).

So this function can identify overlaps where:

  • right_frag is the same as left_frag (full overlap),
  • right_frag fits entirely inside left_frag (substring),
  • right_frag can attach to the end of left_frag (extend beyond its end), or
  • none of the above (return overlap of 0 and set offset to strlen(left_frag)).

This function does NOT attempt to identify overlaps where left_frag can attach to the end of right_frag (extend beyond its end).

For example, the call locate_overlap("hello", "lol", ptr) sets the value pointed to by ptr to 3, and returns 2. This is because the amount of overlap is 2 (the "lo" overlap and has length 2), and the overlap begins at index 3 of "hello" (the index of the second 'l').

The function's header should be:
int locate_overlap(char *left_frag, char *right_frag, int *offset)

Type your C solution code here:


This is a function problem. Write a C function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.


Log In

Need help?

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.