http://qs1969.pair.com?node_id=483477

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.

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

Replies are listed 'Best First'.
Re^3: How to use regular expression for this? (LCS)
by tye (Sage) on Aug 13, 2005 at 02:21 UTC

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

Re^3: How to use regular expression for this? (LCS)
by Anonymous Monk on Aug 14, 2005 at 02:55 UTC
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.