Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re: How to use regular expression for this? (LCS)

by tye (Sage)
on Aug 12, 2005 at 23:53 UTC ( #483463=note: print w/replies, xml ) Need Help??


in reply to How to use regular expression for this?

This looks like what Algorithm::Diff's LCS (longest common subsequence) does. It even has an optimized LCS_length().

- tye        

  • Comment on Re: How to use regular expression for this? (LCS)

Replies are listed 'Best First'.
Re^2: How to use regular expression for this? (LCS)
by AReed (Pilgrim) on Aug 13, 2005 at 01:08 UTC
    I assumed from the example strings given that the positions of the characters within the strings was important. That is, "ABCXXXXXX" would be a good match, but "XABCXXXXX" would not.

    If position is not important then my solution doesn't work at all. If my assumption was correct however, then using Algorithm::Diff::LCSidx to compare the pattern against the target string will work, but requires the additional step of checking to see if the contents of the two arrays of indices pointed to by the returned references are equivalent. Unless I missed something when skimming through the documentation that is.

    Thanks, tye. Hanging out around here I definitely learn something new (usually several somethings) every day.

      Yes, I chose to interpret the problem as described (N characters "in order" with no mention of position) and to interpret the lining up of the positions as merely a typographic choice to make the correspondence more visually obvious.

      There certainly are other ways to interpret the problem and I don't even assert that the interpetation that I chose is the most likely to be correct. (:

      If my assumption was correct however, then using Algorithm::Diff::LCSidx to compare the pattern against the target string will work, but requires the additional step of checking to see if the contents of the two arrays of indices pointed to by the returned references are equivalent.

      That'd work for the examples given, but could fail for a case like "CCCDDFFIII".

      - tye        

      Thanks a lot. AReed. Actually in my case the string and the pattern are usually not the same length, generally strings are longer than the length of the pattern. ( so string XXXXXABCXXXXXXXXXXXXXXXXXXX would be a match too.) That is why I initially think about regular expression. I guess I can still use your method by loop through the string and compare the substring with the same length as the pattern.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://483463]
help
Chatterbox?
[ambrus]: Corion: two very hard things about presentations I should try to work on if I have twenty times as much free time as in real life are:
[Corion]: That's why I like HTML - it makes it relatively easy to resize stuff. Resizing with Powerpoint is much harder, or at least, I remember it being that way
[ambrus]: (a) good sans serif fonts optimized for slides in a projector with coverage of the symbols needed for mathematical formulas in a sans serif font matching the text font well, and
[ambrus]: (b) a good presentation system that lets the presenter quickly interactively edit the slides live during a presentation, to combine the advantages of blackboard and overhead slide styles in modern tech
[Corion]: Heh - in university, I cheated on (a) by doing blackboard presentations using chalk. But those were 2 hour presentations, not quick/essential/ reduced presentations where you want to show something quick
[ambrus]: (either on just one screen or two screens). this is necessary because
[ambrus]: overhead slide plus blackboard is inconvenient because the lighting conditions are different and they require separate areas you can't quickly repartition, and typing on keyboard is faster and more convenient than writing on a blackboard
[Corion]: (b) would be cool. I've thought about this doing Pod editing, and even simply regenerating/live updating the browser makes things much more interactive
[ambrus]: modern computers have way enough processing power to allow this, at least for geeks who are willing to spend a few weeks to learn a tricky new user interface like vim
[Corion]: ambrus: Well, for mathematical notation, I find blackboard much more convenient than a computer. But when inserting text or moving text around, the computer wins obviously

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (11)
As of 2017-09-26 10:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    During the recent solar eclipse, I:









    Results (293 votes). Check out past polls.

    Notices?