### String Matchup/Overlap problem

Posted:

**Mon May 04, 2009 4:01 pm**I was recently at a programming competition where one of the problems involved matching up various strings in an order, by determining where they overlap to form one continous string. I do not remember the exact name/specifications of the problem, but would like to find out if there are any similar problems on UVA (haven't managed to find any) which involve matching strings up like this...does anyone know of any? (or anything not on UVA which is related to this)

The problem was basically as follows:

A satellite takes sightings of an area, each sighting which is 5metres long, and represented by a string showing what is in each metre eg: if one sighting sees a 5m area with a tree,house,monument,tree,tree it is represented as THMTT.

In this specific problem, there are 2 areas where an individual sighting could be of. Many different sightings are given, and you are required to seperate the sightings into 2 groups, each group representing its own full area (meaning all sightings in one group are of the same area, and when the strings from that group are put alongside eachother, with overlaps, they form one large string representing the entire area). The problem also had the restriction of there being at most 1 monument per area, and the possibility of it being impossible to determine which area a specific sighting was of.

Does anything know of any similar problem on UVA or elsewhere which involves having to match up strings like this where they overlap, determining their order, spererating them into seperate groups based on where they match, or anything similar?

The problem was basically as follows:

A satellite takes sightings of an area, each sighting which is 5metres long, and represented by a string showing what is in each metre eg: if one sighting sees a 5m area with a tree,house,monument,tree,tree it is represented as THMTT.

In this specific problem, there are 2 areas where an individual sighting could be of. Many different sightings are given, and you are required to seperate the sightings into 2 groups, each group representing its own full area (meaning all sightings in one group are of the same area, and when the strings from that group are put alongside eachother, with overlaps, they form one large string representing the entire area). The problem also had the restriction of there being at most 1 monument per area, and the possibility of it being impossible to determine which area a specific sighting was of.

Does anything know of any similar problem on UVA or elsewhere which involves having to match up strings like this where they overlap, determining their order, spererating them into seperate groups based on where they match, or anything similar?