模仿Pythonstr.查找（子字符串）使用迭代而不是内置函数

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

I can't think of a way to do it without any built-in functions at all.

我可以：

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()，我们会失去一些效率，因为我们可以更快地完成。OP指定了迭代，上面使用了它，但是递归变量更紧凑一些：

^{pr2}$

Answer 2

您可以使用Boyer-Moore或Knuth-Morris-Pratt。两者都会创建表格来预先计算出每次失误时的更快动作。B-M页面有一个python实现。这两个页面都引用了其他字符串搜索算法。在

Answer 3

在不使用find的约束下，可以改用str.index，如果找不到子字符串，则返回ValueError：

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

和用法：

^{pr2}$

如果首先要检查的是tstring字符串的其余部分，那么必须先检查哪个字符串与tstring匹配：

^{3}$

要在不使用字符串方法的情况下执行此操作，请执行以下操作：

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)

我想不出没有任何内置函数的方法。在