模式匹配Python

我目前坚持尝试做一个朴素的算法，它给出了一个模式，例如aabba 在文本中搜索它，例如abbbbaababaabbaaabbaa一次一个字母。它会比较一个与文本，如果这是正确的，然后比较下一个字母，如果这是错误的整个模式将转向一个以b等比较一模式匹配Python

我们给出的代码示例

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（）函数太快了（我需要一种非优化的算法，我使用和for loops语句）。

赞赏任何帮助，感谢

来源

2011-06-01 NewbieCoder

这是功课？如果是这样，请将其标记为。 – 2011-06-01 04:05:54

等待，这是否太快意味着什么？ – 2011-06-01 04:05:57

这听起来像他应该通过它字符本身 – GWW 2011-06-01 04:10:30

我想这里是你需要的，下面的代码是逐字符比较的。您也可以通过迭代在text更换呼叫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

来源

2011-06-01 20:06:15 loudandclear

-1

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

这就是，只要我能理解，你的算法。未经测试，将测试并通知您是否可以使用。

经过测试，似乎工作。

来源

2011-06-01 04:13:01

只是要指出，迭代列表或数组等是关于你可以在Python中做的最糟糕的事情。与C或C++相比，性能受到很大影响。此外，你会想使用正则表达式做这些类型的匹配，以避免错误，一个一个的等... – jcpennypincher 2011-06-01 04:16:36

它的功课，所以... – 2011-06-01 04:18:42

小心使用网络代码时的错误.. 。大声笑 – jcpennypincher 2011-06-01 04:20:06

-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

来源

2011-06-01 04:14:07 jcpennypincher

-1他应该通过它在字符中通过char它在作业标记 – 2011-06-01 04:19:07

注意标题....模式匹配Python。这表明一个正则表达式是可以接受的。你当然可以匹配单个字符和正则表达式。但是，如果你打算遍历数组或字符串，那么使用C或C++ – jcpennypincher 2011-06-01 04:25:03

如果你看了这个问题，它说他想用charcter来做它的字符，这不是正则表达式正在做的事情，它只是找到结果，而他并没有真的写出一个“算法” – 2011-06-01 04:27:51

模式匹配Python

回答

相关问题