How to find longest common substring of words in a list?-CodePudding

I have a list of words:

list1 = ['technology','technician','technical','technicality']

I want to check which phrase is repeated in each of the word. In this case, it is 'tech'. I have tried converting all the characters to ascii values, but I am stuck there as I am unable to think of any logic. Can somebody please help me with this?

CodePudding user response：

This is generally called the Longest common substring/subsequence problem.

A very basic (but slow) strategy:

longest_substring = ""
curr_substring = ""

# Loop over a particular word (ideally, shortest).
for start_idx in range(shortest_word):

    # Select a substring from that word.
    for length in range(1, len(shortest_word) - start_idx):
        curr_substring = shortest_word[start_idx : start_idx   length]

        # Check if substring is present in all words,
        # and exit loop or update depending on outcome.

        if "curr_substring not in all words":
            break

        if "new string is longer":
            longest_substring = curr_substring

CodePudding user response：

Iterate over first word, increase length of prefix if there is only one prefix in all words checked by set, when difference in prefix is found return last result

list1 = ['technology', 'technician', 'technical', 'technicality']


def common_prefix(li):
    s = set()
    word = li[0]
    while(len(s) < 2):
        old_s = s
        for i in range(1, len(word)):
            s.add(word[:i])
    return old_s.pop()


print(common_prefix(list1))

output: techn

CodePudding user response：

Find the shortest word. Iterate over increasingly small chunks of the first word, starting with a chunk equal in length to the shortest word, checking that each is contained in all of the other strings. If it is, return that substring.

list1 = ['technology', 'technician', 'technical', 'technicality']

def shortest_common_substring(lst):
    shortest_len = min(map(len, lst))
    shortest_word = next((w for w in lst if len(w) == shortest_len), None)
    
    for i in range(shortest_len, 1, -1):
        for j in range(0, shortest_len - i):
            substr = lst[0][j:i]
            
            if all(substr in w for w in lst[1:]):
                return substr

And just for fun, let's replace that loop with a generator expression, and just take the first thing it gives us (or None).

def shortest_common_substring(lst):
    shortest_len = min(map(len, lst))
    shortest_word = next((w for w in lst if len(w) == shortest_len), 0)
    
    return next((lst[0][j:i] for i in range(shortest_len, 1, -1)
                             for j in range(0, shortest_len - i)
                             if all(lst[0][j:i] in w for w in lst[1:])),
                None)