Databases
StackOverflow2013
Postsdbo
POAlgorithm for finding shortest sentence matching a pattern
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgorithm for finding shortest sentence matching a pattern
    primarykey
    data
    text
    <p>I have a problem here which i am trying to solve.</p> <p>The program is given a text file containing the following characters: a - z, A - Z, 0 - 9, fullstop (.) and space . Words in the text file are purely made up of a-z, A-Z and 0-9 . The program receives several queries. Each query is made up of a set of full words already present in the file. The program should return the smallest phrase from the file where all words are present (in any order) . If there are many such phrases, return the first one.</p> <p>Here is an example. Let us say that the file contains:</p> <pre><code>Bar is doing a computer science degree. Bar has a computer at home. Bar is now at home. </code></pre> <p>Query 1 :</p> <pre><code>Bar computer a </code></pre> <p>Response:</p> <pre><code>Bar has a computer </code></pre> <p>Query 2:</p> <pre><code>Bar home </code></pre> <p>Response:</p> <pre><code>home. Bar </code></pre> <p>I thought of this solution. For query 1, Bar is searched first and all three occurences of Bar is assembled as a list. Each node in list also contain the starting position of the smallest phrase and the total length. So it'll look like</p> <p>1st node "Bar, 0, 1" [Query, starting posn, total length]. Similarly for 2nd and 3rd node.</p> <p>Next computer is searched for. The minimum distance of computer for each occurence of Bar is calculated. </p> <p>1st node "Bar Computer", 0, 5</p> <p>2nd node "Bar Computer", 7 , 4 and so on for other nodes</p> <p>Next "a" is searched for. The search has to start from the starting position that is mentioned each node and has to be traversed left and right until the word is found as order is unimportant. The minimum of the occurence has to be chosen. </p> <p>Is this solution on right track? I feel that doing this way, i have to be wary of many cases and there might be a simpler solution available. </p> <p>If the words are unique, it becomes a variant of TSP? </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USexcray
    1. USexcray
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAlgorithm for finding shortest sentence matching a pattern
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    2. VO
      singulars
      1. POAlgorithm for finding shortest sentence matching a pattern
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POAlgorithm for finding shortest sentence matching a pattern
      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