パターンマッチングアルゴリズム

Question

これは、パターンマッチングAlgotithmについての私の大学のクラスからのスライド、それ...

であると私は、以下の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と等しくないかをチェックするのはなぜですか？

Answer 1

それはこれはあなたの場合、内側を反転しなければならなかった場合には!Mismatch

たことと思われるMismatch=noと言われた擬似コードで

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

しているときは、内部での翻訳ミスを犯しましたステートメント。

Answer 2

擬似コードは本質的にすべての点からT（1 <= k <= n-m+1）で始まる可能性があるかどうかをチェックします。 kからk + m-1までのTの部分文字列がPにマッチすることを確認します。一致しない文字が1つ見つかると、部分文字列のチェックを停止し、kをインクリメントして次の位置からチェックします。条件付き（T[k+i-1] != P[i]）は内側ループのブレーク条件であり、ブール値は現在の開始位置kからのフラグです。一致しません。

このアルゴリズムの複雑さは、O(nm)であり、遅いことに注意してください。 KMPのような線形時間で検索できるよりスマートなアルゴリズムがあります。