Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You get bad_alloc error because there are too many unique substrings to fit in memory. To rectify it you may use any approach where there is no need to store every unique substring.</p> <p>My solution is pretty complicated, so I provide just a sketch of an algorithm.</p> <p>It is possible to store only those substrings, that are beginning at every possible position in w1, w2, ......, wn, and ending at the end of w1, w2, ......, wn. And instead of the whole substring, you can store only pointer to its starting character.</p> <p>To answer the queries, you can sort all the queries, sort all the substrings. Then iterate the substrings in the following manner: take all the substrings starting from the same character, then take all the substrings with the same second character and so on. In other words, you <strong>implicitly</strong> construct a trie with all inner nodes having weight 1 and all leaf nodes having weight, equal to the length of the remaining unique substring, corresponding to this node. And you iterate through this trie, computing cumulative sum of each node weight, and comparing it with the next not-yet-processed query. As soon as you find the match, you print the substring and continue with trie traversal.</p> <p>All this requires not much memory but is very hungry for computation resources. But it may be optimized. You may use an explicit trie to store all short substrings (probably with lengths 1 .. 2 or 1 .. 3). Also you may use bucket sort algorithm to sort longer substrings.</p>
    singulars
    1. This table or related slice is empty.
    1. POInterviewStreet Find Strings
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USEvgeny Kluev
    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. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COyah.. seems complicated :) but still thanx.
      singulars
      1. PO
      1. USsachin
    2. CO@gsingh2011: the substrings that end at every possible position are not stored anywhere. Otherwise there may be not enough memory to hold every substring. While we do not store every substring, we may count them as second half of this post explains. Sorted substrings, described here, are, in fact, a [Generalized suffix array](http://en.wikipedia.org/wiki/Suffix_array). Alternative approach is to use a [Generalized suffix tree](http://en.wikipedia.org/wiki/Generalised_suffix_tree) and count nodes in order of depth-first search, but it needs somewhat more memory.
      singulars
      1. PO
      1. USEvgeny Kluev
 

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