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

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.

CodePudding user response：

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

CodePudding user response：

Try this, get the maximum matching length by inverting the string

str1 = "123147"
str2 = "147467"

result = 0
for i in range(len(str2)):
    temp = str2[:i   1]
    if str1.endswith(temp):
        result = len(temp)
print(result)

CodePudding user response：

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]