Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I have a following idea regarding Trie, complexity O(N): You start with empty Trie. You take words one by one, and add word to Trie. After you add a word (let's call it word Wi) to Trie, there are two cases to consider:</p> <ol> <li>Wi is prefix of some of the words you added before. That statement is true if you didn't add any nodes to Trie while adding word Wi. In that case, Wi is prefix and part of our solution.</li> <li>Some of the words added before are prefix of Wi. That statement is true if you passed through node that represents end of some word added before (let's cal that word Wj). In that case, Wj is prefix of Wi and part of our solution. </li> </ol> <p>In more details (pseudocode):</p> <pre><code>for word in words add word to trie if size of trie did not change then // first case add word to result if ending nodes found while adding word // second case add words defined by those nodes to result return result </code></pre> <p>Adding new word to Trie:</p> <pre><code>node = trie.root(); for letter in word if node.hasChild(letter) == false then // if letter doesnt exist, add it node.addChild(letter) if letter is last_letter_of_word then // if last letter of word, store that info node.setIsLastLetterOf(word) node = node.getChild(letter) // move </code></pre> <p>While you are adding new word, you can also check if you passed through any nodes that represent last letters of other words. Complexity of algorithm that I described is O(N). Another important thing is that this way you can know how many times word Wi prefixes other words, which may be useful.</p> <p>Example for {aab, aaba, aa}: Green nodes are nodes detected as case 1. Red nodes are nodes detected as case 2. Each column(trie) is one step. At the beginning trie is empty. Black arrows show which nodes we visited(added) in that step. Nodes that represent last letter of some word have that word written in parenthesess.</p> <p><img src="https://i.stack.imgur.com/RSROO.png" alt="enter image description here"></p> <ol> <li>In step 1 we add word aab. </li> <li>In step 2 we add word aaba, recognize one case 2 (word aab) and add word aab to result.</li> <li>In step 3 we add word aa, recognize case 1 and add word aa to result.</li> </ol> <p>At the end we have result = {aab, aa} which is correct.</p>
    singulars
    1. This table or related slice is empty.
    1. POFind strings which are prefixes of other strings
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USMartinsos
    1. USMartinsos
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFind strings which are prefixes of other strings
      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. VTUpMod
    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