Search String Algorithm in Table
I wrote some code in Python to solve this problem. Python is designed to be very readable. There is a plaintext explanation of the algorithm below to help you understand what's going on. I am treating the database as an array indexable by its columns and rows.

def find_match(db, input_string):
    if input_string == '':
        return list()
    matches = list()
    length = 0
    for row in db:
        for col in [w1, w2, w3, w4]:
            if len(input_string) == length:
                return list(row[v]) # we found a match!
            if row[col] != input_string[length]:
                length = 0
                break
            length += 1
        if length == 0:
            continue
        if len(input_string) == length:
            return list(row[v]) # we found a match!
        matches.append((length, row[v]))
    matches.sort(reverse=True) # this puts longest matches first 
    for length, match in matches:
        solution = find_match(db, input_string[length:]) 
# input_string[length:] means the input_string from index length till the end.
        if solution != []:
            return list(match) + solution
    return list()


Explanation:

This is a recursive algorithm to match the input. What it does is it loops over all rows in the database and finds all the ones that could be part of a match. If it finds anything that is a complete match, then it returns it immediately (there's no point going any further once you've found a solution.) 

Then it sorts this list of potential matches so that the longest ones are evaluated first. It loops through these sorted matches and calls the find_match function using the portion of the input string that still needs to be matched, if that match is the one to be used. In this way, you are evaluating the longest matches first, as you requested.

A step-by-step example (Example 2 from your question):

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


input_string: [A, B, C, D, F]

input_string is not empty, so we construct matches as an empty list. This is the list of rows that could be part of the final solution (they must entirely match the input string from the beginning until they run out of characters)

We loop over the rows, and find the following potential matches:
X1 (A); Y0 (A, B); Y1 (A, B, C)

We add them to the list as a tuple containing their length and the v that corresponds to them. This way we will be able to make sure we check the longest matches first. matches looks like this once we finish iterating over the db:
[(1, X1), (2, Y0), (3, Y1)]

Next we sort the list using the length as the key so the longest matches are first:
[(3, Y1), (2, Y0), (1, X1)]

Now we iterate over the matches, and try to find a solution using each one. Because we are calling the function recursively, it could be a long time between checking each match, depending on the length of the input string that still needs to be matched.

The first row we try to find a solution with is the first element in matches: Y1 (A, B, C). We call find_match(db, [D, F]) using [D, F] as the input string because that is the portion that still needs to be matched if we use Y1 (A, B, C). We can easily find the input string because we have the length (3, in this case) and so we take input_string from its 3rd index on:

A, B, C, D, F
0, 1, 2, 3, 4
X  X  X  D, F


input_string: [D, F]

we loop over the rows and find only one match: X4 (D)

Our list of matches is [(1, X4)], so we call find_match(db, [F])

input_string: [F]

we loop over the rows and find 0 matches, so matches is [] and when we iterate over it, we immediately continue on to the next block of code which tells us to return []. This is our way of saying we didn't find any match.

Now we go back to when input_string was [D, F]. We set solution equal to [], because that's what we just returned. Our only potential match was (X4, D), which we just checked, so now we are done iterating over the potential matches. Because we couldn't find any match with [D, F] as the input string we return [] as well.

Now we go back to when [A, B, C, D, F] was the input string and we had just finished trying to match Y1. We continue iterating over matches ([(3, Y1), (2, Y0), (1, X1)]). We call find_match(db, [C, D, F]) using Y0 (A, B) as the match.

input_string: [C, D, F]

We loop over the rows and we would get X3 (C); Y3 (C, D, F); Y4 (C, D, G) as our matches, but once we find that Y3 (C, D, F) exactly matches the input string, we go ahead and return [Y3]

Now we go back to when [A, B, C, D, F] was the input string and we were just using Y1 (A, B, C) as the match. At this point we see that we did find a match (the function returned [Y3]) and we add Y1 to it so that we have the full match: [Y1, Y3]. We return that and the function is done executing.

In the part of the function that compares the row with the input string, there is a little bit of bounds checking to make sure we only take as many characters from the row as it has, and we don't try to match the input string with a row that is longer than it is, but I didn't bother elaborating on that because it never came up in this example.