字符串匹配替代方法

試圖寫我自己的快速模式匹配算法。不想使用語言特定的解決方案。我專注於編寫算法。這是因爲我正在閱讀不同的技術來進行字符串匹配。有些複雜但非常有趣，像拉賓卡布等我想出了這種方法，它是快速和線性的。它適用於我嘗試過的不同輸入。所以我在想，有沒有什麼理由不應該使用這種方法而不是非常熟悉的方法。基本上我正在拍攝一段文字，並與該模式的相應字符進行比較 - 一次一個。另外，如果有人能指出我的錯誤 - 這將會很棒。謝謝您的答覆和意見提前:)字符串匹配替代方法

public static boolean patternMatch(String pattern, String text) 
{ 
    if(pattern == null) 
     return true; 
    if(text == null) 
     return false; 

    char[] patternArray = pattern.toCharArray(); 
    char[] textArray = text.toCharArray(); 

    int length = pattern.length(); 
    int j = 0; 
    for(char t : textArray) 
    { 
     if(t == patternArray[j]) 
     { 
      j++; 
      if(j == length) 
       return true; 
     } 
     else { 
      j = 0; 
      if(t == patternArray[j]) j++; 
     } 
    } 
    return false; 
}

來源

2014-09-05 ND27

該方法的要求是什麼？你沒有發佈，所以不可能說它是好還是壞。你能舉一些你想要完成的例子嗎？ – 2014-09-05 02:35:02

控制問題：如果文本包含重複序列（如「xyxyz」並將其與「xyz」匹配），那麼您的方法會按照您的要求做什麼？ – 2014-09-05 02:36:00

您的編程語言或運行時是否包含像IndexOf或Contains這樣的字符串方法？如果是這樣，你爲什麼不使用它們？ – 2014-09-05 02:36:57

兩個原因使用標準方法：

很容易寫，簡單地做了錯誤的事情的方法。你的方法就是這樣，因爲它不能匹配字符串「aab」的模式「ab」。（它匹配模式的第一個「a」和字符串，然後不匹配字符串的第二個「a」的b，然後繼續查看是否可以從第三個字符開始匹配字符串。）
標準方法是快速。你的算法是線性的，這是非常好的（如果它也是正確的！）。然而，許多字符串匹配算法將在次線性時間內工作。也就是說，匹配字符串所花費的時間在輸入問題的大小上增長得比線性緩慢。也許很難相信，但確實如此。（請閱讀文獻以獲得有關此索賠的證據。）

來源

2014-09-05 02:44:50

字符串匹配替代方法

回答

相關問題