使用迭代而非内置函数模拟Python的str.find(substring)

Question

我该如何在Python中找到一个字符串里子字符串的位置，而不使用str.find()呢？我应该怎么循环呢？

def find substring(string,substring):
     for i in xrange(len(string)):
        if string[i]==substring[0]:
          print i
        else: print false

举个例子，当string = "ATACGTG"，而substring = "ACGT"时，它应该返回2。我想了解一下str.find()是怎么工作的。

Answer 1

在不使用 find 的情况下，你可以用 str.index 来代替。如果找不到子字符串，它会返回一个错误信息（ValueError）：

def find_substring(a_string, substring):
    try:
        print(a_string.index(substring))
    except ValueError:
        print('Not Found')

用法如下：

>>> find_substring('foo bar baz', 'bar')
4
>>> find_substring('foo bar baz', 'quux')
Not Found

如果你必须要循环的话，可以这样做，这样可以在字符串中滑动查找。如果第一个字符匹配了，就再检查后面的部分是否以子字符串开头，这样就算找到了：

def find_substring(a_string, substring):
    for i, c in enumerate(a_string):
        if c == substring[0] and a_string[i:].startswith(substring):
            print(i)
            return
    else: 
        print(False)

如果不使用任何字符串方法，可以这样做：

def find_substring(a_string, substring):
    for i in range(len(a_string)):
        if a_string[i] == substring[0] and a_string[i:i+len(substring)] == substring:
            print(i)
            return
    else: 
        print(False)

我想不出完全不使用任何内置函数的方法。

Answer 2

我想不出任何完全不使用内置函数的方法。

我可以这样做：

def find_substring(string, substring):

    def starts_with(string, substring):
        while True:
            if substring == '':
                return True

            if string == '' or string[0] != substring[0]:
                return False

            string, substring = string[1:], substring[1:]

    n = 0

    while string != '' and substring != '':

        if starts_with(string, substring):
            return n

        string = string[1:]

        n += 1

    return -1

print(find_substring('ATACGTG', 'ACGT'))

也就是说，避免使用内置的 len()、range() 等等。因为不使用内置的 len()，我们会失去一些效率，因为本来可以更快完成。提问者提到要使用迭代，这里用的是迭代的方法，但递归的写法会更简洁一些：

def find_substring(string, substring, n=0):

    def starts_with(string, substring):
        if substring == '':
            return True

        if string == '' or string[0] != substring[0]:
            return False

        return starts_with(string[1:], substring[1:])

    if string == '' or substring == '':
        return -1

    if starts_with(string, substring):
        return n

    return find_substring(string[1:], substring, n + 1)

print(find_substring('ATACGTG', 'ACGT'))

Answer 3

你可以使用 Boyer-Moore 或者 Knuth-Morris-Pratt 这两种方法。这两种方法都会创建一些表格，提前计算出在每次没有找到时，如何更快地移动搜索的位置。Boyer-Moore 的页面上有 Python 的实现代码。而这两个页面也提到了其他一些字符串搜索的算法。