Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Nice question for an excercise in basic string-operations. I didnt remember the suffix-tree anymore ;) But as you have stated: theory-wise, you are set.</p> <h2>How do I preprocess the tree with descendant leaves?</h2> <p>The <a href="http://en.wikipedia.org/wiki/Longest_repeated_substring_problem" rel="nofollow">wikipedia-stub</a> onto this topic is a bit confusing. You only need to know, if you are the outermost non-leaf-node with <code>n &gt;= k</code> childs. If you found the substring from the root-node to this one in the whole string, the suffix-tree tells you, that there are <code>n</code> possible continuitations. So there must be <code>n</code> places, where this string occurs.</p> <h2>After that, how can I quickly compute depth?</h2> <p>A simple key-concept of this and many similar problems is to do a depth-first-search: In every Node, ask the child-elements for their value and return the maximum of it to the parent. The root-node will get the final result. </p> <p>How the values are calculated differs between the problems. Here you have three possiblilitys for every node:</p> <ol> <li>The node have no childs. Its a leaf-node, the result is invalid.</li> <li>Every child returns an invalid result. Its the last non-leaf-node, the result is zero (no more characters after this node). If this node have <code>n</code> childs, the concated string of every edge from the root to this node appears <code>n</code> times in the whole string. If we need at least <code>k</code> nodes and <code>k &gt; n</code>, the result is also invalid.</li> <li>One or more leafs return something valid. The result is the maximum of the returned value <strong>plus</strong> the length of the string attached the edge to it.</li> </ol> <p>Of course, you also have to return the correspondending node. Otherwise you will know, how long the longest repeated substring is but not where it is. </p> <h2>Code</h2> <p>You should try to code this by yourself first. Constructing the tree is simple but not trivial if you want to gather all necessary informations. Nevertheless here is a simple example. Please note: every sanity-checking is dropped out and everything will fail horribly, if the input is somehow invalid. E.g. do not try to use any other root-index than one, do not refere to nodes as a parent, which weren't referenced as a childs before, etc. Much room for improvement *<em>hint</em>;)*.</p> <pre><code>class Node(object): def __init__(self, idx): self.idx = idx # not needed but nice for prints self.parent = None # edge to parent or None self.childs = [] # list of edges def get_deepest(self, k = 2): max_value = -1 max_node = None for edge in self.childs: r = edge.n2.get_deepest() if r is None: continue # leaf value, node = r value += len(edge.s) if value &gt; max_value: # new best result max_value = value max_node = node if max_node is None: # we are either a leaf (no edge connected) or # the last non-leaf. # The number of childs have to be k to be valid. return (0, self) if len(self.childs) == k else None else: return (max_value, max_node) def get_string_to_root(self): if self.parent is None: return "" return self.parent.n1.get_string_to_root() + self.parent.s class Edge(object): # creating the edge also sets the correspondending # values in the nodes def __init__(self, n1, n2, s): #print "Edge %d -&gt; %d [ %s]" % (n1.idx, n2.idx, s) self.n1, self.n2, self.s = n1, n2, s n1.childs.append(self) n2.parent = self nodes = {1 : Node(1)} # root-node string = sys.stdin.readline() k = int(sys.stdin.readline()) for line in sys.stdin: parent_idx, child_idx, start, length = [int(x) for x in line.split()] s = string[start-1:start-1+length] # every edge constructs a Node nodes[child_idx] = Node(child_idx) Edge(nodes[parent_idx], nodes[child_idx], s) (depth, node) = nodes[1].get_deepest(k) print node.get_string_to_root() </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POLongest repeated (k times) substring
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USPeter Schneider
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POLongest repeated (k times) substring
      singulars
      1. PTQuestion
    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. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

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