Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>NOTE: I don't normally write two answers and if you feel that it is tacky, feel free to comment on this one and note vote it up. This answer is a more optimized solution, but I wanted to give the most straightforward one I could think of first and then put this in another answer to not confuse the two. Basically they are for different audiences.</p> <p>The key to solving this problem efficiently is to not throw away information you have about shorter common substrings when looking for longer ones. Naively, you check each substring against the other one, but if you know that "AB" matches in "ABC", and your next character is C, don't check to see if "ABC" is in "ABC", just check that the spot after "AB" is a "C". </p> <p>For each character in A, you have to check up to all the letters in B, but because we stop looking through B once a longer substring is no longer possible, it greatly limits the number of checks. Each time you get a longer match up front, you eliminate checks on the back-end, because it will no longer be a longer substring. </p> <p>For example, if A and B are both long, but contain no common letters, each letter in A will be compared against each letter in B for a runtime of A*B. </p> <p>For a sequence where there are a lot of matches, but the match length isn't a large fraction of the length of the shorter string, you have A * B combinations to check against the shorter of the two strings (A or B) leading to either A*B*A or A*B*B, which is basically O(n^3) time for similar length strings. I really thought the optimizations in this solution would be better than n^3 even though there are triple-nested for loops, but it appears to not be as best as I can tell. </p> <p>I'm thinking about this some more, though. Either the substrings being found are NOT a significant fraction of the length of the strings, in which case the optimizations don't do much, but the comparisons for each combination of A*B don't scale with A or B and drop out to be constants -- OR -- they are a significant fraction of A and B and it directly divides against the A*B combinations that have to be compared.</p> <p>I just may ask this in a question.</p> <pre><code>int lcs(char * A, char * B) { int length_a = strlen(A); int length_b = strlen(B); // these hold the position in A of the longest common substring int longest_length_found = 0; // for each character in one string (doesn't matter which), look for incrementally larger strings in the other for (int a_index = 0; a_index &lt; length_a - longest_length_found; a_index++) { for (int b_index = 0; b_index &lt; length_b - longest_length_found; b_index++) { // offset into each string until end of string or non-matching character is found for (int offset = 0; A[a_index+offset] != '\0' &amp;&amp; B[b_index+offset] != '\0' &amp;&amp; A[a_index+offset] == B[b_index+offset]; offset++) { longest_length_found = longest_length_found &gt; offset ? longest_length_found : offset; } } } return longest_found_length; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POlongest common subsequence: why is this wrong?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USxaxxon
    1. USxaxxon
    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
    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