Skip to main content
Computer Science

Return to Question

Post Reopened by Evil, Rick Decker, D.W.♦
further explained the requirements of the algorithm, namely that the elements near the beginning of the output must have as long a string as possible.
Source Link
edit approved Jul 1, 2016 at 10:50
Jon McClung
edit approved Jul 1, 2016 at 10:50
Jon McClung
  • 157
  • 4

There exists an input with expected output based on a string search/match on the table:

Example 1:

input = [ A, B, C, D, E ]

expected_output => [ Y1, X4, X5 ]

Explanation:

We're. What we are trying to do is match the input with a combination of rows from the tabledatabase. From each row we take allThe only portion of the row that we use for matching is from wiw1 entriesto (iw4 is from 1 to 4), except the ones which have no data. We then represent this row using itsuse the v entrycolumn to identify the row. So, not itsfor example, the input string idE would produce output X5, while input A, B would produce output Y0.

We In the case that there is no exact match, we want the elements closer to find the longest match forfront of the inputlist to represent as long a string as possible. For example, so we look forwith input A, B, C, D, E.

This is nowhere to be found, so we checkcould match a number of ways, notably A, BY1, CX4, DX5.

Still no luck, so we look for AX1, BY2, CX5.

This matches Y1, so that is We prefer the first part of our resultformer, assuming it results in a complete match. Next we need to findbecause DA, EB, C (the rest of the input), but there is no match.

We look for D, and findfrom Y4Y1. Our partial solution) is longer than Y1, Y4A.

Finally we look for E and find(from Y5X1). We want the first item in the output to represent as long a string as possible, completingand only when two potential outputs have the match. The full solution then is Y1, Y4, Y5same length for the initial item do we try to get the longest second item we can.

input = [A, B, C, D, F ]A, B, C, D, F

expected_output => [ Y0, Y3 ] Y0, Y3

There exists an input with expected output based on a string search/match on the table:

Example 1:

input = [ A, B, C, D, E ]

expected_output => [ Y1, X4, X5 ]

Explanation:

We're trying to match the input with a combination of rows from the table. From each row we take all of the wi entries (i is from 1 to 4), except the ones which have no data. We then represent this row using its v entry, not its id.

We want to find the longest match for the input, so we look for A, B, C, D, E.

This is nowhere to be found, so we check A, B, C, D.

Still no luck, so we look for A, B, C.

This matches Y1, so that is the first part of our result, assuming it results in a complete match. Next we need to find D, E (the rest of the input), but there is no match.

We look for D, and find Y4. Our partial solution is Y1, Y4.

Finally we look for E and find Y5, completing the match. The full solution then is Y1, Y4, Y5.

input = [A, B, C, D, F ]

expected_output => [ Y0, Y3 ]

There exists an input with expected output based on a string search/match on the table. What we are trying to do is match the input with a combination of rows from the database. The only portion of the row that we use for matching is from w1 to w4. We then use the v column to identify the row. So, for example, the input string E would produce output X5, while input A, B would produce output Y0. In the case that there is no exact match, we want the elements closer to the front of the list to represent as long a string as possible. For example, with input A, B, C, D, E we could match a number of ways, notably Y1, X4, X5, X1, Y2, X5. We prefer the former, because A, B, C (from Y1) is longer than A (from X1). We want the first item in the output to represent as long a string as possible, and only when two potential outputs have the same length for the initial item do we try to get the longest second item we can.

input = A, B, C, D, F

expected_output => Y0, Y3

added explanation of what the user is looking for.
Source Link
edit approved Jun 30, 2016 at 7:49
Jon McClung
edit approved Jun 30, 2016 at 7:49
Jon McClung
  • 157
  • 4
DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y1Y0
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

There existexists an input with expected output basingbased on a string search  / matchmatch on the table:

Example 1:

input = [ A, B, C, D, E ]

expected_output => [ Y1, X4, X5 ]

Explanation:

We're trying to match the input with a combination of rows from the table. From each row we take all of the wi entries (i is from 1 to 4), except the ones which have no data. We then represent this row using its v entry, not its id.

We want to find the longest match for the input, so we look for A, B, C, D, E.

This is nowhere to be found, so we check A, B, C, D.

Still no luck, so we look for A, B, C.

This matches Y1, so that is the first part of our result, assuming it results in a complete match. Next we need to find D, E (the rest of the input), but there is no match.

We look for D, and find Y4. Our partial solution is Y1, Y4.

Finally we look for E and find Y5, completing the match. The full solution then is Y1, Y4, Y5.

expected_output => [ Y1, X3, X4, X5 ]Example 2:

expected_output => [ Y1, Y3 ]

expected_output => [ Y0, Y3 ]

Explanation:

The inputWe would like to find A, B, C, D, F, but there is no match.

Likewise, we would match A, B, C, D if we could, but we cannot.

We do find Y1 is a list of stringsmatch for A, B, C, so we use that. Our partial solution is Y1.

Now we look for D, F, but we don't find it.

We find X4 matches D, so our partial solution is Y1, X4.

Next we look for F but then being processedthere is no match. At this point we backtrack until we find a solution that does work. We take X4 off our solution and look for a better match for D, but there is no other way to check ifmatch it, and we can't match a sequence exist in the tableshorter substring, because that would be empty.

We take - ItY1 off our solution (now it is empty) and look for another way to match A, B, C. There is no other way, so we look for A, B, which we find with Y0. Our partial solution is Y0.

Now we search for the longest possible match first then fallback toremainder of the smallest matchinput, C, D, F and we find it with Y3. Our solution is Y0, Y3.

DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y1
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

There exist an input with expected output basing on a string search  / match on the table:

input = [ A, B, C, D, E ]

expected_output => [ Y1, X3, X4, X5 ]

expected_output => [ Y1, Y3 ]

The input is a list of strings that is then being processed to check if a sequence exist in the table - It search for the longest possible match first then fallback to the smallest match.

DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y0
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

There exists an input with expected output based on a string search/match on the table:

Example 1:

input = [ A, B, C, D, E ]

expected_output => [ Y1, X4, X5 ]

Explanation:

We're trying to match the input with a combination of rows from the table. From each row we take all of the wi entries (i is from 1 to 4), except the ones which have no data. We then represent this row using its v entry, not its id.

We want to find the longest match for the input, so we look for A, B, C, D, E.

This is nowhere to be found, so we check A, B, C, D.

Still no luck, so we look for A, B, C.

This matches Y1, so that is the first part of our result, assuming it results in a complete match. Next we need to find D, E (the rest of the input), but there is no match.

We look for D, and find Y4. Our partial solution is Y1, Y4.

Finally we look for E and find Y5, completing the match. The full solution then is Y1, Y4, Y5.

Example 2:

expected_output => [ Y0, Y3 ]

Explanation:

We would like to find A, B, C, D, F, but there is no match.

Likewise, we would match A, B, C, D if we could, but we cannot.

We do find Y1 is a match for A, B, C, so we use that. Our partial solution is Y1.

Now we look for D, F, but we don't find it.

We find X4 matches D, so our partial solution is Y1, X4.

Next we look for F but then there is no match. At this point we backtrack until we find a solution that does work. We take X4 off our solution and look for a better match for D, but there is no other way to match it, and we can't match a shorter substring, because that would be empty.

We take Y1 off our solution (now it is empty) and look for another way to match A, B, C. There is no other way, so we look for A, B, which we find with Y0. Our partial solution is Y0.

Now we search for the remainder of the input, C, D, F and we find it with Y3. Our solution is Y0, Y3.

Post Closed as "Needs details or clarity" by David Richerby, D.W.♦
Source Link
Raven
Raven
  • 109
  • 2

Search String Algorithm in Table

For a given database table:

DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y1
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

There exist an input with expected output basing on a string search / match on the table:

input = [ A, B, C, D, E ]

expected_output => [ Y1, X3, X4, X5 ]

input = [A, B, C, D, F ]

expected_output => [ Y1, Y3 ]

The input is a list of strings that is then being processed to check if a sequence exist in the table - It search for the longest possible match first then fallback to the smallest match.

Question:

What algorithms could I use or learn to be able to solve this efficiently?

What is the pseudocode or high level overview of how to solve the problem?