How to find a match of words in two strings?

Question

I have two strings like

My name is Bogdan and Bogdan and I am from Russia

I need to get word Bogdan from this strings. I always know what end of first sentence == start of second sentence.

How can I find this overlapping.

My solution returns similar chars

res = list(set('My name is Bogdan').intersection(set('Bogdan and i am from Russia')))
print(res)

Returns

['i', 'n', 'g', 'm', ' ', 's', 'B', 'a', 'd', 'o']

Answer 1

You start by overlapping the two strings maximally and then iterate by reducing the overlap:

def find_overlap(s1, s2):
    for i in range(len(s1)):
        test1, test2 = s1[i:], s2[:len(s1) - i]
        if test1 == test2:
            return test1

s1, s2 = "My name is Bogdan", "Bogdan and I am from Russia"
find_overlap(s1, s2)
# 'Bogdan'
s1, s2 = "mynameisbogdan", "bogdanand"
find_overlap(s1, s2)
# 'bogdan'

As you can see this also works if the two strings do not contain spaces.

This has O(n) runtime, but could be reduced to O(min(n, m)) if you first determine which of the two strings is shorter.

If you expect the string to find to be much shorter than even the shortest of the two strings, you can make this even O(k), where k is the length of the string to find by starting with a minimal overlap:

def find_overlap(s1, s2):
    for i in range(1, len(s1) + 1):
        if i == len(s2):
            return None
        test1, test2 = s1[-i:], s2[:i]
        if test1 == test2:
            return test1