Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Can the unit sequence contain repetitions of its own? Do you know the length of the unit sequence?</p> <p>e.g.</p> <pre><code>ABCABCABCDEFABCABCABCDEFABCABCABCDEF </code></pre> <p>where the unit sequence is <code>ABCABCABCDEF</code></p> <p>If the answer is yes, you've got a difficult problem, I think, unless you know the length of the unit sequence (in which case the solution is trivial, you just make a state machine that first stores the unit sequence, then verifies that the each element rest of the sequence corresponds to each element of the unit sequence). </p> <p>If the answer is no, use this variant <a href="http://en.wikipedia.org/wiki/Cycle_detection" rel="nofollow">Floyd's cycle-finding algorithm</a> to identify the unit sequence:</p> <ul> <li>Initialize pointers P1 and P2 to the beginning of the sequence.</li> <li>For each new element, increment pointer P1 every time, and increment pointer P2 every other time (keep a counter around to do this).</li> <li><p>If P1 points to an identical elements of P2, you've found a unit sequence.</p></li> <li><p>Now repeat through the rest of the sequence to verify that it consists of duplicates.</p></li> </ul> <hr> <p><strong>UPDATE:</strong> you've clarified your problem to state that the unit sequence may contain repetitions of its own. In this case, use the cycle-finding algorithm, but it's only guaranteed to find potential cycles. Keep it running throughout the length of the sequence, and use the following state machine, starting in state 1:</p> <p>State 1: no cycle found that works; keep looking. When the cycle-finding algorithm finds a potential cycle, verify that you've gotten 2 copies of a preliminary unit sequence from P, and go to state 2. If you reach the end of the input, go to state 4.</p> <p>State 2: preliminary unit sequence found. Run through the input as long as the cycle repeats identically. If you reach the end of the input, go to state 3. If you find an input element that is different from the corresponding element of the unit sequence, go back to state 1.</p> <p>State 3: The input is a repetition of a unit sequence if the end of the input consists of complete repetitions of the unit sequence. (If it's midway through a unit sequence, e.g. <code>ABCABCABCABCAB</code> then a unit sequence found, but it does not consist of complete repetitions.)</p> <p>State 4: No unit sequence found.</p> <p>In my example (repeating <code>ABCABCABCDEF</code>) the algorithm starts by finding ABCABC, which would put it in state 2, and it would stay there until it hit the first DEF, which would put it back in state 1, then probably jump back and forth between states 1 and 2, until it reached the 2nd ABCABCABCDEF, at which point it would re-enter state 2, and at the end of the input it would be in state 3.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow should I find repeated word sequences
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJason S
    1. USJason S
    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
    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