プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

Knuth-Morris-Prattアルゴリズム


Knuth Morris Pratt(KMP)は、文字を左から右にチェックするアルゴリズムです。パターンにサブパターンが複数存在する場合、最悪の場合でも、そのプロパティを使用して時間計算量を改善します。

KMPの時間計算量はO(n)です。

入力と出力

Input:
Main String: “AAAABAAAAABBBAAAAB”, The pattern “AAAB”
Output:
Pattern found at location: 1
Pattern found at location: 7
Pattern found at location: 14

アルゴリズム

findPrefix(pattern、m、prefArray)

入力- パターン、パターンの長さ、プレフィックスの場所を格納する配列

出力- プレフィックスが配置されている場所を格納する配列

Begin
   length := 0
   prefArray[0] := 0

   for all character index ‘i’ of pattern, do
      if pattern[i] = pattern[length], then
         increase length by 1
         prefArray[i] := length
      else
         if length ≠ 0 then
            length := prefArray[length - 1]
            decrease i by 1
         else
            prefArray[i] := 0
   done
End

kmpAlgorithm(テキスト、パターン)

入力: 検索されるメインテキストとパターン

出力- パターンが見つかった場所

Begin
   n := size of text
   m := size of pattern
   call findPrefix(pattern, m, prefArray)

   while i < n, do
      if text[i] = pattern[j], then
         increase i and j by 1
      if j = m, then
         print the location (i-j) as there is the pattern
         j := prefArray[j-1]
      else if i < n AND pattern[j] ≠ text[i] then
         if j ≠ 0 then
            j := prefArray[j - 1]
         else
            increase i by 1
   done
End

#include<iostream>
using namespace std;

void findPrefix(string pattern, int m, int prefArray[]) {
   int length = 0;
   prefArray[0] = 0;     //first place is always 0 as no prefix

   for(int i = 1; i<m; i++) {
      if(pattern[i] == pattern[length]) {
         length++;
         prefArray[i] = length;    
      }else {
         if(length != 0) {
            length = prefArray[length - 1];
            i--;     //decrease i to avoid effect of increasing after iteration
         }else
            prefArray[i] = 0;
      }
   }
}

void kmpPattSearch(string mainString, string pattern, int *locArray, int &loc) {
   int n, m, i = 0, j = 0;
   n = mainString.size();
   m = pattern.size();
   int prefixArray[m];    //prefix array as same size of pattern
   findPrefix(pattern, m, prefixArray);
   loc = 0;

   while(i < n) {
      if(mainString[i] == pattern[j]) {
         i++; j++;
      }

      if(j == m) {
         locArray[loc] = i-j;      //item found at i-j position.
         loc++;
         j = prefixArray[j-1];    //get the prefix length from array
      }else if(i < n && pattern[j] != mainString[i]) {
         if(j != 0)
            j = prefixArray[j-1];
         else
            i++;
      }
   }
}

int main() {
   string str = "AAAABAAAAABBBAAAAB";
   string patt = "AAAB";
   int locationArray[str.size()];
   int index;
   kmpPattSearch(str, patt, locationArray, index);

   for(int i = 0; i<index; i++) {
      cout << "Pattern found at location: " <<locationArray[i] << endl;
   }
}

出力

Pattern found at location: 1
Pattern found at location: 7
Pattern found at location: 14

  1. フォードファルカーソンアルゴリズム

    Ford-Fulkersonアルゴリズムは、特定のグラフの開始頂点からシンク頂点への最大フローを検出するために使用されます。このグラフでは、すべてのエッジに容量があります。 SourceとSinkという名前の2つの頂点が提供されます。ソース頂点にはすべて外向きのエッジがあり、内向きのエッジはありません。シンクにはすべて内向きのエッジがあり、外向きのエッジはありません。 いくつかの制約があります: エッジのフローは、そのグラフの所定の容量を超えません。 流入フローと流出フローも、ソースとシンクを除くすべてのエッジで等しくなります。 入力と出力 入力:隣接行列:0 10 0 10 0

  2. フロイドウォーシャルアルゴリズム

    Floyd-Warshallアルゴリズムを使用して、特定の重み付きグラフからすべてのペアの最短経路問題を見つけます。このアルゴリズムの結果として、グラフ内の任意のノードから他のすべてのノードまでの最小距離を表す行列が生成されます。 最初、出力行列はグラフの指定されたコスト行列と同じです。その後、出力行列はすべての頂点kを中間頂点として更新されます。 このアルゴリズムの時間計算量はO(V ^ 3)です。ここで、Vはグラフ内の頂点の数です。 入力と出力 Input: The cost matrix of the graph. 0 3 6 ∞ ∞ ∞ &