Longest common prefix based on elements

Question

I have an array of string elements in an array:

["000", "1110", "01", "001", "110", "11"]

For an element in the array,

• I want to find the previous element index with longest common prefix.

• If I have multiple matching elements then select the nearest element index.

• If none found then just select previous index.

Example:

["000", "1110", "01", "001", "110", "11"]

Output:
[0,1,1,1,2,5]

a) "000" - output is 0, because we do not have any previous elements.
b) "1110" - output is 1, no previous element with longest prefix so select previous index.
c) "01" - output is 1,"000" has longest prefix, so its index is 1.
d) "001" - output is 1, "000" has longest prefix, so its index is 1.
e) "110" - output is 2,  "1110" has longest prefix, so its index 2.
f) "11" - output 5, "110" is most nearest element with longest prefix so its index 5.

I am not able to understand what approach I need to take for this task. Can you please help me.

Answer 1

Using a trie makes it pretty easy to find the longest common prefix so far in time linear in the total number of characters in the input. In Python (sorry):

import collections


class Trie:
    def __init__(self):
        self._children = collections.defaultdict(Trie)
        self._previous_index = 0

    # Find the longest prefix of word that appears in the trie,
    # return the value of _previous_index at that node.
    def previous_index(self, word):
        node = self
        for letter in word:
            child = node._children.get(letter)
            if child is None:
                break
            node = child
        return node._previous_index

    # Ensure that each of the prefixes of word exists in the trie.
    # At each node corresponding to a prefix, set its _previous_index to index.
    def insert(self, index, word):
        self._previous_index = index
        node = self
        for letter in word:
            node = node._children[letter]
            node._previous_index = index


def longest_common_prefix_indexes(words):
    trie = Trie()
    for index_minus_one, word in enumerate(words):
        print(trie.previous_index(word))
        trie.insert(index_minus_one + 1, word)


longest_common_prefix_indexes(["000", "1110", "01", "001", "110", "11"])