Re: Identifying Overlapping Area in a Set of Strings

Well the following replaces the front of the strings as per your spec, I couldn't be arsed to do the end of the strings, as you need to know in advance where the next string starts (and if its before the endpoint of your current string). If might be best to search first and save the start/end positions of the substrings first and then go through replacing values.

This should be a good start though.

#!/perl -w
use strict;

my $string = "abcdefghijklmnopqrstuvwxyz";
my @sub_strings = ('cdef', 'efghij', 'klmno', 'mnopqrst');

my $string_index = 0;
my $last_end_point = 0;
foreach my $sub_string (@sub_strings) {
    
    my $string_index = index($string, $sub_string, $string_index);
    die ("Couldn't find string") if $string_index == -1;

    my $overlap = $last_end_point - $string_index;
    if ($overlap > 0) {
        substr($sub_string, 0, $overlap) = '-'x$overlap;
    }
    $last_end_point = $string_index + (length($sub_string));
}
print join(',', @sub_strings);
[download]

update: removed stupid variable declaration

---
my name's not Keith, and I'm not reasonable.

Comment on Re: Identifying Overlapping Area in a Set of Strings Download Code

Replies are listed 'Best First'.

Re^2: Identifying Overlapping Area in a Set of Strings
by reasonablekeith (Deacon) on Jul 29, 2005 at 10:31 UTC

rnahi

Anyway a BIG caveat to all this is that these result are ambiguous if there could be multiple matches for a given substring. For example searching for "GG" twice in "GGGG" could give you.

 ORG:  "GGGG";
 SUB   "GG"
         "GG"; # no overlapping
 or
       "--"
       "--";  # full overlapping

It's hard to say which is best, you need to look more closely at what you're trying to acheve.

regardless my updated code is as follows...

#!/perl -w
use strict;

my $string = "abcdefghijklmnopqrstuvwxyz";
my @sub_strings = ('cdef', 'efghij', 'klmno', 'mnopqrst');

my $string_index = 0;
my $last_end_point = index($string, $sub_strings[0]) + length($sub_str
+ings[0]);

foreach my $sub_array_index (1..$#sub_strings) {

    my $string_index = index($string, $sub_strings[$sub_array_index], 
+$string_index);
    my $overlap = $last_end_point - $string_index;

    # if there's an overlap replace from the front of current string, 
+and the
    # end of the previous string
    if ($overlap > 0) {
        substr($sub_strings[$sub_array_index], 0, $overlap) = '-'x$ove
+rlap;
        substr($sub_strings[$sub_array_index-1], -$overlap, $overlap) 
+= '-'x$overlap;
    }

    $last_end_point = $string_index + length($sub_strings[$sub_array_i
+ndex]);
}
[download]

updated

tlm

---
my name's not Keith, and I'm not reasonable.

[reply]
[d/l]


Don't ask to ask, just ask
	PerlMonks