CODEWITHSUNDEEP
pythonpython-3.xalgorithm
4daJKong
4daJKong

Reputation: 2045

How to get the intersection of two strings in this situation?

I have two strings:

str1 = "123147"
str2 =    "1474671231"

the end of str1 has some similar part with the start of str2 ("147"), and I want to find the length of this similar part, so I tried to:

for ch in str1:
    if ch == str2[0]:
        start_idx = len(str1) - date.index(ch)
        break

However the problem is it will return a mistake if the begin of str1 is same as the begin of str2 ("1") and if I reverse the checking order, it still have this problem ("7"). Is there any simple method to solve it?

Most important, I only want to check the end of str1 and the beginning of str2, and ignore other parts, for example, "1231" in str1 and str2 should be ignored.

Upvotes: 2

Views: 134

Answers (2)

Riccardo Bucco
Riccardo Bucco

Reputation: 15364

A possible approach is to use a regex, and concat strings in a smart way:

import re

C = '#'
result = len(re.findall(r'^(\w*).*\1$', str2 + C + str1)[0])

The assumption here is that both str1 and str2 do not contain character C.

Another solution (which has optimal complexity, i.e. it's very fast compared to other approaches when you're dealing with long strings, but is clearly more complicated than what you need):

def longest_prefix_suffix(str1, str2):
    n = min(len(str1), len(str2))
    lps = [0] * n
    l = 0
    i = 1
    while i < n:
        if str1[i] == str2[l]:
            l += 1
            lps[i] = l
            i += 1
        else:
            if l != 0:
                l = lps[l - 1]
            else:
                lps[i] = 0
                i = i + 1
    return lps[n - 1]

Upvotes: 0

trincot
trincot

Reputation: 350310

It does not seem a problem to just try all suffixes of str1, starting with the longest:

def intersection_length(str1, str2):
    for i in range(max(0, len(str2) - len(str1), len(str1))):
        if str2.startswith(str1[i:]):
            return len(str1) - i
    return 0

Run as:

str1 = "12314755"
str2 = "14755467"
print(intersection_length(str1, str2))  # 5

Upvotes: 2

Related Questions