模式匹配Python
模式匹配Python
提问于 2011-06-01 12:02:58
我目前一直在尝试制作一个朴素的算法，它给出一个模式的一部分，例如在文本中搜索它，例如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 loops语句)。
感谢您的帮助，谢谢
回答 3
Stack Overflow用户
回答已采纳
发布于 2011-06-02 04:06:16
我猜这就是你需要的，下面的代码进行逐个字符的比较。您还可以将对find的调用替换为text上的迭代，其中包括检查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:
-1Stack Overflow用户
发布于 2011-06-01 12:13:02
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据我所知，这是你的算法。未测试，将测试并让您知道它是否工作。
经过测试，似乎可以正常工作。
Stack Overflow用户
发布于 2011-06-01 12:14:07
听起来您正在学习正则表达式，这里有一段代码片段可以帮助您入门。
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/6196128
复制相关文章
相似问题
腾讯云开发者
