Databases
StackOverflow2013
Postsdbo
POWhich algorithm to use to get longest string matching in two big arrays?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhich algorithm to use to get longest string matching in two big arrays?
    primarykey
    data
    text
    <p>The problem is easy to explain: we have two big arrays (32 bit integer values) and we have to find all common sequences above a given number of consecutive position (n).</p> <p>For instance, if n=3 and arrays to compare are:</p> <pre><code>a = [1, 3, 5, 7, 3, 2, 7, 4, 6, 7, 2, 1, 0, 4, 6] b = [2, 5, 7, 3, 2, 3, 4, 5, 6, 3, 2, 7, 4, 6, 0] </code></pre> <p>The algoritmh should return, two arrays:</p> <pre><code>r0 = [5, 7, 3, 2] r1 = [3, 2, 7, 4, 6] </code></pre> <p>(or better, its relative positions to first array and the number of consecutive bytes matched).</p> <p>I believe a good point to start is the <a href="http://en.wikipedia.org/wiki/Longest_common_substring_problem" rel="nofollow">Longest Common Substring Algorithm</a>, but perhaps anybody knows an algorithm that fits better or exactly with my problem.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USIvan
    1. USIvan
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhich algorithm to use to get longest string matching in two big arrays?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhich algorithm to use to get longest string matching in two big arrays?
      1. USpimvdb
      1. VTFavorite
    3. VO
      singulars
      1. POWhich algorithm to use to get longest string matching in two big arrays?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI belive this belongs on [Math.stackexchange](http://math.stackexchange.com/)
      singulars
      1. POWhich algorithm to use to get longest string matching in two big arrays?
      1. USgenesis
    2. COThis is an open research problem often studied in the context of matching/aligning DNA sequences. You might have some better luck researching how folks are doing this with DNA, or even find some available libraries.
      singulars
      1. POWhich algorithm to use to get longest string matching in two big arrays?
      1. USMark Elliot
    3. CO@Mark: How is this an open research problem?
      singulars
      1. POWhich algorithm to use to get longest string matching in two big arrays?
      1. USNeil G
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload