Perl-Sensitive Sunglasses PerlMonks

### Re^2: Longest Common Subsequence

by Limbic~Region (Chancellor)
 on May 16, 2006 at 19:47 UTC ( #549876=note: print w/replies, xml ) Need Help??

in reply to Re: Longest Common Subsequence

If you understood the mental process I went through to create the Longest Common Subsequence, it should not be hard to see how to adapt it to the Longest Common Substring.

Once we have a list of character positions across strings, we can create ordered piles where each mapping has a difference of 1 in each position with its adjacent neighbors. You can get rid of the need for looping to find mappings greater because you can predict the values they should contain. Then you just need to find the largest pile and that represents the LCS (S = substring).

Arrays are replaced with hashes. Picking a hash key at random, you place it in a new pile and then predict the next mapping. If that key exists you place it on the same pile. You repeat this process until you have no more mappings. You then start back at the beginning of the pile and look for smaller items. Once no more items fit in that pile, you move on to the next hash key.

```use Algorithm::Loops 'NestedLoops';
use List::Util 'reduce';

my @str = map {chomp; \$_} <DATA>;
print LCS(@str), "\n";

sub LCS{
my @str = @_;
my @pos;
for my \$i (0 .. \$#str) {
my \$line = \$str[\$i];
for (0 .. length(\$line) - 1) {
my \$char= substr(\$line, \$_, 1);
push @{\$pos[\$i]{\$char}}, \$_;
}
}
my \$sh_str = reduce {length(\$a) < length(\$b) ? \$a : \$b} @str;
my %map;
CHAR:
for my \$char (split //, \$sh_str) {
my @loop;
for (0 .. \$#pos) {
next CHAR if ! \$pos[\$_]{\$char};
push @loop, \$pos[\$_]{\$char};
}
my \$next = NestedLoops([@loop]);
while (my @char_map = \$next->()) {
my \$key = join '-', @char_map;
\$map{\$key} = \$char;
}
}
my @pile;
for my \$seq (keys %map) {
push @pile, \$map{\$seq};
for (1 .. 2) {
my \$dir = \$_ % 2 ? 1 : -1;
my @offset = split /-/, \$seq;
\$_ += \$dir for @offset;
my \$next = join '-', @offset;
while (exists \$map{\$next}) {
\$pile[-1] = \$dir > 0 ? \$pile[-1] . \$map{\$next} : \$map{
+\$next} . \$pile[-1];
\$_ += \$dir for @offset;
\$next = join '-', @offset;
}
}
}
return reduce {length(\$a) > length(\$b) ? \$a : \$b} @pile;
}
__DATA__
qwertyJoyzhnac
Jyzshuaqwertyb
Joyzqwertybbc
Yqwertyblah

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: note [id://549876]
help
Chatterbox?
 [Eily]: can't you just remote connect to the linux machine ? [marto]: IIRC the hiemdal suite made life much easier on windows, and people on XDA developers put out released of windows only pages for adb that made it less of a pain [marto]: Eily you can't remote connect the physical device via USB ;) [Corion]: Eily: Sure, that's what I do, but some things you need to do on the Android device directly, like when navigating the bootloader :-) [Eily]: marto you just need a longer cable :P [Corion]: marto: Yeah, but I'm somewhat wary of installing random USB drivers downloaded from mega.nz , Google Drive or whatever, so Linux wins there due to there being no conflicts and me just having to edit one text file in the worst case, to add the USB vendor [hippo]: Long USB cable FTW. [Corion]: Eily: I've thought of that, but I don't like running long cables through the appartment because sooner or later I'll trip over it, pulling at least one device off its stand :) [marto]: hmm, may have to patch CPAN::Meta to move from search.cpan to metacpan in the META.json/yml files [Corion]: marto: Heh - it seems that they plan to keep the search.cpan.org links alive for a long time. But still, I plan on moving PM to use/generate the new links

How do I use this? | Other CB clients
Other Users?
As of 2018-05-23 09:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (166 votes). Check out past polls.

Notices?