模式匹配算法

這是從類幻燈片在我的大學，它大約模式匹配Algotithm .. enter image description here 模式匹配算法

我嘗試將它下面的Java代碼;

  // Get values for both the text T1,T2 ... Tn and the pattern P1 P2 ... Pm 
      String[] T = {"Java", "is", "too", "delicious", ", Dr.Java", "is", "confrim!"}; 
      String[] P = { "is", "too"}; 
      // Get values for n and m, the size of the text and the pattern, respectively 
      int n = T.length; 
      int m = P.length; 
      // Set k1 the starting location for the attempted match, to 1 
      int k = 0; 

      // While(k<=(n-m+1))do 
      while (k <= (n - m + 1) - 1) { 
        // Set the value of i to 1 
        int i = 0; 
        // Set the value of Mismatch NO 
        boolean Mismatch = true; // Not found (true - NO) 

        // While both (i<=m) and (Mismatch = NO) do 
        while ((i <= m - 1) && (Mismatch)) { // if Not found (true - NO) 
          // if Pi != Tk+(i-1) then 
          if (P[i].equals(T[k])) { // if Found(true) 
            // Set Mismatch to YES 
            Mismatch = false; // Found (false - YES) 
            // Else 
          } else { 
            // Increment i by 1 (to move to the next character) 
            i = i + 1; 
          } 
          // End of the loop 
        } 
        // If mismatch = NO then 
        if (!Mismatch) { // if Found (false - YES) 
          // Print the message 'There is a match at position' 
          System.out.print("There is a match at position "); 
          // Print the value of k 
          System.out.println(k); 
        } 
        // Increment k by 1 
        k = k + 1; 
        // Enf of the loop 
      } 
      // Stop, we are finished

但我有一個問題！爲什麼在僞代碼版本中，檢查P是否不等於T？我認爲它寧願檢查P是否等於T（它與我的版本有什麼不同，對我可怕的英語感到抱歉）

來源

2011-06-18 Smile.Hunter

您在內部做了一個翻譯錯誤，而

while ((i <= m - 1) && (Mismatch)) { // if Not found (true - NO)

在僞代碼，有人說是Mismatch=no這將是!Mismatch

這導致的情況下，你必須顛倒內，如果聲明。

來源

2011-06-18 18:21:37 Omnaest

謝謝！但我如何解決它？我嘗試更改&&（！Mismatch）和！（P [i] .equals（T [k]）），但它不起作用。 –

@Smile您是否在if語句塊中將不匹配設置爲true？ – Omnaest

我嘗試了這兩個，但仍然不明白.. –

僞代碼本質上檢查每一個匹配可能在T開始的點（1 <= k <= n-m+1），循環並檢查從k到k + m-1的T的子字符串是否與P匹配。因此，只要發現一個不匹配的字母，它就會停止檢查子字符串，並增加k（以檢查下一個位置）。該條件（T[k+i-1] != P[i]）是內部循環的破壞條件，並且標記來自當前起始位置k的布爾值不存在匹配。

請注意，該算法的複雜性爲O(nm)，這很慢。有更聰明的算法可以在線性時間內搜索，如KMP。

來源

2011-06-18 18:17:25 davin

模式匹配算法

回答

相關問題