字符串中子串的基本索引递归（Python）

1 投票

6 回答

5319 浏览

提问于 2025-04-16 23:09

我正在自学基础编程。
我有一个简单的项目，就是找出一个字符串中某个子字符串出现的位置索引。比如在字符串 "abcdefdef" 中，子字符串 "def" 的位置应该是 3 和 6。我写了一些代码，但没有得到我想要的结果。以下是我写的代码。

注意：我知道可能有更简单的方法可以得到结果，比如使用语言自带的功能或库，比如正则表达式。我也明白我的方法可能不是最优的算法。不过现在，我只是想得到一些关于如何修正我下面逻辑的建议，而不是使用更标准的方法。

import string

def MIT(String, substring): # "String" is the main string I'm searching within
    String_list = list(String)
    substring_list = list(substring)
    i = 0
    j = 0
    counter = 0
    results = []
    while i < (len(String)-1):
        if [j] == [i]:
            j = j + 1
            i = i + 1
            counter  = counter + 1
            if counter == len(substring):
                results.append([i - len(substring)+1])
                counter = 0
                j = 0
                i = i+1
        else:
            counter = 0
            j = 0
            i = i+1
    print results
    return

我的思路是这样的。我把字符串和子字符串都变成一个列表。这样就可以对字符串中的每个字母进行索引。我把 i 和 j 都设为 0——这将是我在字符串和子字符串中的起始索引。我还有一个新变量，叫做 counter，初始值设为 0。基本上，我用 counter 来计算位置 [i] 的字母和位置 [j] 的元素相等的次数。如果 counter 等于子字符串的长度，那么我就知道 [i - len(substring) + 1] 是我的子字符串开始的位置，所以我把它加到一个叫做 results 的列表中。然后我重置 counter 和 j，继续寻找更多的子字符串。

我知道这段代码有点笨拙，但我觉得我应该还是能得到答案的。结果却是：

>>> MIT("abcdefghi", "def")
[[3]]
>>> MIT("abcdefghi", "efg")
[[3]]
>>> MIT("abcdefghi", "b")
[[1]]
>>> MIT("abcdefghi", "k")
[[1]]

有什么想法吗？

列表操作字符串处理代码调试算法优化递归算法字符串索引子字符串查找基础编程

6 个回答

正则表达式模块（re）更适合这个任务。

好的参考资料： http://docs.python.org/howto/regex.html

还有： http://docs.python.org/library/re.html

编辑：一种更“手动”的方法可能是使用切片。

s = len(String)
l = len(substring)
for i in range(s-l+1):
    if String[i:i+l] == substring:
        pass #add to results or whatever

回答于 2025-04-16 由 Python大师

分享举报

主要的问题有以下几点：

比较的时候，使用：if String[i] == substring[j]
当找到匹配时，你把i加了两次，去掉第二次加的那一次。
循环应该一直进行到while i < len(String):

当然，它也不会找到重叠的匹配（比如：MIT("aaa", "aa")）

还有一些小问题，比如说这段代码不是特别符合Python的风格，没有必要构建列表，i += 1写起来更清晰，实用的函数应该返回值而不是打印出来等等……

如果你想要高效且正确的代码，可以看看经典的算法书籍：http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844。里面有一整章讲字符串搜索。

如果你想要一个符合Python风格的解决方案，但又不想自己实现整个过程，可以看看其他的回答。

回答于 2025-04-16 由 Python大师

分享举报

我不太清楚你是想学习一些好的字符串搜索算法，还是想找一个简单的方法在Python中实现。如果是后者，那么string.find就是你的好帮手。像这样：

def find_all_indexes(needle, haystack):
    """Find the index for the beginning of each occurrence of ``needle`` in ``haystack``. Overlaps are allowed."""
    indexes = []
    last_index = haystack.find(needle)
    while -1 != last_index:
        indexes.append(last_index)
        last_index = haystack.find(needle, last_index + 1)
    return indexes


if __name__ == '__main__':
    print find_all_indexes('is', 'This is my string.')

虽然这是一种比较简单的方法，但应该很容易理解。

如果你想找一种使用更少标准库的方法（而且实际上会教你一个在实现库时常用的算法），你可以尝试实现Boyer-Moore字符串搜索算法。

回答于 2025-04-16 由 Python大师

分享举报

字符串中子串的基本索引递归（Python）

6 个回答

撰写回答