Python中的模式匹配

Question

我现在遇到一个问题，想要做一个简单的算法。这个算法的任务是，从一段模式，比如说“aabba”，去文本中查找，比如“abbbbaababaabbaaabbaa”，每次只比较一个字母。它会先把模式的第一个字母“a”跟文本中的字母比较，如果对了，就继续比较下一个字母；如果错了，那就把整个模式往后移动一个位置，再把“a”跟下一个字母“b”比较，依此类推。

我们得到了一个代码示例：

print "Input text: ",
text = raw_input()
print "Input pattern: ",
pattern = raw_input()

index = text.find(pattern)
while index > -1:
    print index
    index = text.find(pattern, index+1)

但是Python里的find()函数太快了（我需要一个不那么优化的算法，可能需要用到while和for循环语句）。

任何帮助都非常感谢，

谢谢！

Answer 1

听起来你正在学习正则表达式，这里有一段代码可以帮助你入门。

myFileName = "abbababaaa"
patternToMatch = "ababa"

i = 0
j = 0
while (i < len(myFileName)):
    if (patternToMatch[i:i] == myFileName[j:j]):
        i++
        j++
    else:
        i = 0        

if len(patternToMatch) == i:
    # matched a pattern

Answer 2

def my_find(haystack, needle):
    n_len = len(needle)
    start = 0
    while start <= (len(haystack)-n_len+1):
        if haystack[start:start+n_len-1] == needle:
            return True
        start += 1

这是我理解的你的算法。还没有测试，等我测试一下，如果有效果会告诉你。

测试过了，似乎可以正常工作。

Answer 3

我想你需要的是这样的，下面的代码是逐个字符进行比较的。你也可以用循环来替代对find的调用，这样可以检查text的第一个字符是否和pattern的第一个字符相匹配：

def my_find(text, pattern):
    '''Find the start index of a pattern string in a text.
    Return -1 if not found, and assume that pattern is not empty'''

    found = False
    current_start_index = text.find(pattern[0])
    index_text = current_start_index
    index_pattern = 0

    while not found and index_text + len(pattern) - 1 < len(text) and \
            current_start_index != -1:

        index_text += 1
        index_pattern += 1

        while index_text < len(text) and \
                index_pattern < len(pattern) and \
                text[index_text] == pattern[index_pattern]:

            if index_pattern == len(pattern) - 1:
                found = True
                break
            else:
                index_text += 1
                index_pattern += 1

        if not found:
            current_start_index = text.find(pattern[0],current_start_index + 1)
            index_text = current_start_index

    if found:
        return current_start_index
    else:
        -1