Johnnywang,

If I understand the problem correctly, then from an algorithmic standpoint, what you are looking for is unrealistic, at least to be solved in any reasonable amount of time. The problem is this: the only way to guarantee finding every common continuous subsequence of any length is to do it by brute force. You have to check every subsequence from size m up to the size of the smallest sequence.

In the example you give, you have to check every subsequence from size 2 to size 5. I did a quick math check (so the exact number might be wrong), but the number of check would be in the neighborhood of 600. And this is with only 3 sequences of sizes 11, 11, and 5. Just adding 1 number to each of the 3 sequences would add hundreds of more required checks. The growth of the problem with every additional sequence is polynomial.

For you to want to check 1000's of sequences that may be 1000's of numbers long would require in the billions of required checks which would take much longer than I'm sure you are willing to accept. This is one of those NP problems that CS majors learn about in algorithm classes (traveling salesman, coloring problem, hamiltonian circuit problem, etc).

If someone can come up with an algorithm that is not brute force, thus making the problem not NP, I would love to see it.

davidj

In reply to Re: Seeking algorithm for finding common continous sub-patterns by davidj
in thread Seeking algorithm for finding common continous sub-patterns by johnnywang

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.