Databases
StackOverflow2013
Postsdbo
POSubstring with greatest ratio
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSubstring with greatest ratio
    primarykey
    data
    text
    <p>Let's assume I have some sequence containing <code>{A,B}</code> and there is at least one occurrence of each letter in a sequence. How to find substring within sequence that fulfill requirements:</p> <ul> <li>number of A's to number of B's should be highest possible ratio (#A/#B --> max)</li> <li>if there are many substring with same ratio we have to return longest possible substring</li> <li>finally if there are many of them with same length, we had to return the one with lower beginning index </li> </ul> <p>As output we want index of beginning of found substring and it's length.</p> <p>Example</p> <pre><code>IN: AAABAA OUT: index = 0, length = 6 (ratio is 5 : 1) IN: BABAABBA OUT: index = 1, length = 4 (ratio is 3 : 1) </code></pre> <p>Any hints how to approach problem?</p> <p>As a request I'm adding my thoughts:</p> <ol> <li>If some two groups of consecutive A's are separated with 3 or more B's there's no reason to test it further. It's quite simple because if we had substring like: <code>...A{k}BBBA{m}...</code> ratio is <code>(k+m):3</code> whereas <code>k:1</code> or <code>m:1</code> must give better option</li> <li><p>I tried also finding all longest substrings of A's in sequence. I thought it would be highly propable that my sequence would be something like <code>A{N1}BA{N2}BA{N3}</code> but later on I found it not necesearily true for instance:</p> <p>BABAABBAAA</p></li> </ol> <p>As we can see there are two sequence with same ratio:</p> <ol> <li>i=1 length=4</li> <li>i=6 length=4</li> </ol> <p>But as rule 3rd implies I should return the first one wheres as I said my algorithm was based on longest consecutive A's in sequence.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USabc
    1. USabc
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POSubstring with greatest ratio
      1. USDukeling
      1. VTFavorite
    1. COtell us what you tried. at least the brute force solution with asymptotic complexity.
      singulars
      1. POSubstring with greatest ratio
      1. USKaroly Horvath
    2. CO@KarolyHorvath I've edited orginal post with what I've tried.
      singulars
      1. POSubstring with greatest ratio
      1. USabc
    3. COhttp://stackoverflow.com/questions/8103050/what-exactly-is-the-brute-force-algorithm
      singulars
      1. POSubstring with greatest ratio
      1. USKaroly Horvath
 

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