模式匹配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

回答

相關問題