从Python字符串中删除子字符串。

Question

我想写一个函数，它接受两个输入：一个字符串和一个子字符串，然后该函数将从该字符串中删除该子字符串。

def remove_substring(s, substr):
   """(str, str) -> NoneType
Returns string without string substr

remove_substring_from_string("Im in cs", "cs")
Im in
    """
    other_s = ''
for substr in s:
    if substr in s:
        continue

我该怎么继续？假设我的逻辑是正确的。

- Michel Hijazin

---

你的第一个任务是找到s中子字符串的位置。你的for循环遍历s中的字符。由于s始终是来自s的字符，因此s中的substr始终为True。所以这不是你想要的。你需要做的第一件事是找到s中substr的位置，你可以通过迭代可能找到子字符串的位置，在该位置取一个字符串切片（使用子字符串的长度计算切片的结尾），并检查该切片是否等于子字符串。 - kindall

很棒，你能展示一个代码示例吗？ - Michel Hijazin

remove_substring_from_string("aaa", "aa") 的期望输出是仅有 "a" 还是一个空字符串？即，重叠部分应该如何处理？ - dranjohn

Answer 1

避免使用Python函数。 方法1

def remove_substring_from_string(s, substr):
    '''
    find start index in s of substring
    remove it by skipping over it
    '''
    i = 0
    while i < len(s) - len(substr) + 1:
        # Check if substring starts at i
        if s[i:i+len(substr)] == substr:
            break   
        i += 1
    else:
        # break not hit, so substr not found
        return s
    
    # break hit
    return s[:i] + s[i+len(substr):]

方法二

如果可以使用range函数，上述内容可以更加简洁地写成如下形式。

def remove_substring_from_string(s, substr):
    '''
    find start index in s of substring
    remove it by skipping over it
    '''
    for i in range(len(s) - len(substr) + 1):
        if s[i:i+len(substr)] == substr:
            break
    else:
        # break not hit, so substr not found
        return s
    
    return s[:i] + s[i+len(substr):]

测试

print(remove_substring_from_string("I have nothing to declare except my genuis", " except my genuis"))
# Output: I have nothing to declare'

- DarrylG

Answer 2

这种方法基于KMP算法：

def KMP(s):
    n = len(s)
    pi = [0 for _ in range(n)]

    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        
        if s[i] == s[j]:
            j += 1
        
        pi[i] = j
    
    return pi

# Removes all occurences of t in s
def remove_substring_from_string(s, t):
    n = len(s)
    m = len(t)
    
    # Calculate the prefix function using KMP
    pi = KMP(t + '\x00' + s)[m + 1:]
    r = ""

    i = 0
    while i + m - 1 < n: # Before the remaining string is smaller than the substring
        if pi[i + m - 1] == m: # If the substring is here, skip it
            i += m
        else: # Otherwise, add the current character and move to the next
            r += s[i]
            i += 1
    
    # Add the remaining string
    r += s[i:]
    return r

它的时间复杂度为O(|s| + |t|)，但有一些缺点：

- 代码冗长且不直观。 - 它要求输入字符串中没有null（\x00）。 - 对于短的s和t，其常数因子相当糟糕。 - 它不能像你想象的那样处理重叠的字符串： remove_substring_from_string("aaa", "aa") 将返回 "a"。唯一的保证是对于任意两个字符串s和t，t in remove_substring_from_string(s, t) 都为 False。

可以在这里找到KMP算法的C++示例和进一步解释 here。然后 remove_substring_from_string 函数只检查每个位置是否匹配整个子字符串，如果匹配，则跳过该子字符串。

- dranjohn

Answer 3

我会使用re来完成这个任务。

import re


def remove_substring(s, substr):
    # type: (str, str) -> str
    return re.subn(substr, '', s)[0]

remove_substring('I am in cs', 'cs')
# 'I am in '

remove_substring('This also removes multiple substr that are found. Even if that substr is repeated like substrsubstrsubstr', 'substr')
# 'This also removes multiple  that are found. Even if that  is repeated like '

- Sam Bourne

Answer 4

def remove_substring(s, substr):
while s != "":
    if substr in s:
        s = s.replace(substr, "")
    else:
        return s

if s == "":
    return "Empty String"

这里的想法是我们将 s 中所有出现的 substr 替换掉，通过替换第一个 substr 实例并循环直到完成。

- Farooq